169. 多数元素

题目

解答

方法一：Boyer-Moore 投票算法

class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var candidate = 0
        var count = 0
        for num in nums {
            if count == 0 {
                candidate = num
                count += 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 = nums
        numbers.sort(by: >)
        return numbers[nums.count / 2]
    }
}