今天分享的題目來源于 LeetCode 上第 169 號問題：求眾數(shù)（求數(shù)組中超過一半的數(shù)字）。題目難度為 Easy，目前通過率為 45.8% 。
最后一種解法 Cool ?。?！
題目描述
給定一個大小為 n 的數(shù)組，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。
你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在眾數(shù)。
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
題目解析
題目意思很好理解：給你一個數(shù)組，里面有一個數(shù)字出現(xiàn)的次數(shù)超過了一半，你要找到這個數(shù)字并返回。
解法一：暴力解法
遍歷整個數(shù)組，同時統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)。
最后將出現(xiàn)次數(shù)大于一半的元素返回即可。
動畫描述
代碼實現(xiàn)
class Solution {
public int majorityElement(int[] nums) {
int majorityCount = nums.length/2;
for (int num : nums) {
int count = 0;
for (int elem : nums) {
if (elem == num) {
count += 1;
}
}
if (count > majorityCount) {
return num;
}
}
}
}
復(fù)雜度分析
時間復(fù)雜度：O(n2)
暴力解法包含兩重嵌套的 for 循環(huán)，每一層 n 次迭代，因此時間復(fù)雜度為 O(n2) 。
空間復(fù)雜度：O(1)
暴力解法沒有分配任何與輸入規(guī)模成比例的額外的空間，因此空間復(fù)雜度為 O(1)。
解法二：哈希表法
這個問題可以視為查找問題，對于查找問題往往可以使用時間復(fù)雜度為 O(1) 的 哈希表，通過以空間換時間的方式進行優(yōu)化。
直接遍歷整個 數(shù)組 ，將每一個數(shù)字（num）與它出現(xiàn)的次數(shù)（count）存放在 哈希表 中，同時判斷該數(shù)字出現(xiàn)次數(shù)是否是最大的，動態(tài)更新 maxCount，最后輸出 maxNum。
動畫描述
代碼實現(xiàn)
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
// maxNum 表示元素，maxCount 表示元素出現(xiàn)的次數(shù)
int maxNum = 0, maxCount = 0;
for (int num: nums) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
if (count > maxCount) {
maxCount = count;
maxNum = num;
}
}
return maxNum;
}
}
復(fù)雜度分析
時間復(fù)雜度：O(n)
總共有一個循環(huán)，里面哈希表的插入是常數(shù)時間的，因此時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(n)
哈希表占用了額外的空間 O(n)，因此空間復(fù)雜度為 O(n)。
解法三：摩爾投票法
再來回顧一下題目：尋找數(shù)組中超過一半的數(shù)字，這意味著數(shù)組中其他數(shù)字出現(xiàn)次數(shù)的總和都是比不上這個數(shù)字出現(xiàn)的次數(shù) 。
即如果把 該眾數(shù)記為 +1 ，把其他數(shù)記為 ?1 ，將它們?nèi)考悠饋?，和是大?0 的。
所以可以這樣操作：
- 設(shè)置兩個變量 candidate 和 count，candidate 用來保存數(shù)組中遍歷到的某個數(shù)字，count 表示當前數(shù)字的出現(xiàn)次數(shù)，一開始 candidate 保存為數(shù)組中的第一個數(shù)字，count 為 1
- 遍歷整個數(shù)組
- 如果數(shù)字與之前 candidate 保存的數(shù)字相同，則 count 加 1
- 如果數(shù)字與之前 candidate 保存的數(shù)字不同，則 count 減 1
- 如果出現(xiàn)次數(shù) count 變?yōu)?0 ，candidate 進行變化，保存為當前遍歷的那個數(shù)字，并且同時把 count 重置為 1
- 遍歷完數(shù)組中的所有數(shù)字即可得到結(jié)果
動畫描述
代碼實現(xiàn)
class Solution {
public int majorityElement(int[] nums) {
int candidate = nums[0], count = 1;
for (int i = 1; i < nums.length; ++i) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] == candidate) {
count++;
} else{
count--;
}
}
return candidate;
}
}
復(fù)雜度分析
時間復(fù)雜度：O(n)
總共只有一個循環(huán)，因此時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(1)
只需要常數(shù)級別的額外空間，因此空間復(fù)雜度為 O(1)。
?? 看完三件事：
如果你覺得這篇內(nèi)容對你挺有啟發(fā)，我想邀請你幫我三個忙：
- 點贊，讓更多的人也能看到這篇內(nèi)容（收藏不點贊，都是耍流氓 -_-）
- 關(guān)注我和專欄，讓我們成為長期關(guān)系
- 關(guān)注公眾號「五分鐘學(xué)算法」，第一時間閱讀最新的算法文章，公眾號后臺回復(fù) 1024 送你 50 本 算法編程書籍。
