【题目描述】
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
【示例1】
输入: [3,2,3]
输出: 3
【示例2】
输入: [2,2,1,1,1,2,2]
输出: 2
【思路1】哈希表
1、遍历一遍 遍历一遍数组 使用map记录
2、返回次数大于 ⌊ n/2 ⌋ 的元素
3、时间复杂度O(n)
4、空间复杂度O(n)
func majorityElement(_ nums: [Int]) -> Int {
var map = [Int:Int]()
for num in nums {
var value = map[num] ?? 0
value+=1
map[num] = value
}
for (k,v) in map {
if v > nums.count/2 {
return k
}
}
return 0
}
【思路2】排序
1、如果所有单调递增或者单调递减的数组，那么这个数组的众数为arr[ ⌊ n/2 ⌋]
2、时间复杂度O(nlogn)
3、空间复杂度O(n)
4、LeetCode上内部给的例子报错！
func majorityElement(_ nums: [Int]) -> Int {
let arr = nums.sorted()
return arr[nums.count/2]
}
【思路3】抵消思想，也叫摩尔投票算法 <这个想法好牛🐂>
1、初始化 众数 num 和 count
2、遍历数组，我们假设第一个数就是众数 num
3、当是众数的时，count+1，是其他数时 count-1，当count==0时，下一个数又被当成是众数，依次遍历数组，这样来回抵消，最后count肯定会大于1，那么返回最后的num即可
4、时间复杂度O(n) 线性时间
5、空间复杂度O(1)
func majorityElement(_ nums: [Int]) -> Int {
var count = 0
var tmp = 0
for num in nums {
if count == 0 {
tmp = num
}
count+=(tmp == num) ? 1 : -1
}
return tmp
}
``