169. 多数元素

题目

解答

方法一：Boyer-Moore 投票算法

class Solution {func majorityElement(_ nums: [Int]) -> Int {var candidate = 0var count = 0for num in nums {if count == 0 {candidate = numcount += 1} else {if candidate == num {count += 1} else {count -= 1}}}return candidate}
}

引申：Swift 的内置排序算法 sort() 在 Swift5 之后采用了 TimSort，相较于之前的 Introsort 更 stability，TimSort 是一种混合算法, 核心原理是 切割 + 合并, 时间复杂度是 O(nlogn)

---

方法二：排序

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n / 2 的元素（下标从 0 开始）一定是众数。

class Solution {func majorityElement(_ nums: [Int]) -> Int {// 如果数组中的元素是整形，字符串，结构体等简单数据类型，那么当你将一个数组赋值给另外的数组时，数组中的元素会被拷贝一份，两个数组中的元素相互独立var numbers = numsnumbers.sort(by: >)return numbers[nums.count / 2]}
}