【題目描述】
給定一個大小為 n 的數(shù)組，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。
你可以假設數(shù)組是非空的析命，并且給定的數(shù)組總是存在眾數(shù)。
【示例1】
輸入: [3,2,3]
輸出: 3
【示例2】
輸入: [2,2,1,1,1,2,2]
輸出: 2
【思路1】哈希表
1伊滋、遍歷一遍 遍歷一遍數(shù)組 使用map記錄
2碳却、返回次數(shù)大于 ? 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昼浦、如果所有單調(diào)遞增或者單調(diào)遞減的數(shù)組，那么這個數(shù)組的眾數(shù)為arr[ ? n/2 ?]
2筒主、時間復雜度O(nlogn)
3关噪、空間復雜度O(n)
4、LeetCode上內(nèi)部給的例子報錯乌妙！
func majorityElement(_ nums: [Int]) -> Int {
let arr = nums.sorted()
return arr[nums.count/2]
}
【思路3】抵消思想使兔，也叫摩爾投票算法 <這個想法好牛??>
1、初始化 眾數(shù) num 和 count
2藤韵、遍歷數(shù)組虐沥，我們假設第一個數(shù)就是眾數(shù) num
3、當是眾數(shù)的時泽艘，count+1欲险，是其他數(shù)時 count-1，當count==0時匹涮，下一個數(shù)又被當成是眾數(shù)天试，依次遍歷數(shù)組，這樣來回抵消然低，最后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
}
``