給定一個大小為 n 的數組，找到其中的眾數。眾數是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。
你可以假設數組是非空的，並且給定的數組總是存在眾數。
示例 1:
輸入: [3,2,3] 輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2] 輸出: 2
解析：
題目咋一看感覺穩了有木有，解題思路出奇的清晰啊：構造一個hash存儲結構，將數組中元素值作為key，該元素出現的次數作為value存放在hash中，遍歷hash找出第一個value大於n/2的key返回即可。
public static int majorityElement(int[] nums) {
Map hash = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer temp = null;
hash.put(nums[i], null != (temp = hash.get(nums[i]))?++temp:1);
}
for (Integer in : hash.keySet()) {
if (hash.get(in) > (nums.length/2)) {
return in;
}
}
return 0;
}
可以看出如上思路的代碼實現時間複雜度O(n),空間複雜度也為O(n)。
那麼，問題來了，有沒有更高效（無論從時間上和空間上）的方式來解決這個問題呢？
答案是有的，採用摩爾投票法，其算法思想為：將數組中的第一個數假設為眾數，然後進行統計其出現的次數，如果遇到同樣的數，則計數器自增1，否則計數器自減1，如果計數器減到了0，則更換下一個數字為候選者。
public static int majorityElement1(int[] nums) {
//假設第一個節點為目標節點
int temp = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
//若上次循環累積次數為零，則更新當前節點為目標節點並設累計次數為1
if (0 == count) {
temp = nums[i];
count = 1;
}else {
//否則累加或者累減
if (nums[i] == temp) {
count++;
}else {
count--;
}
}
}
return temp;
}
可見此實現的時間複雜度為O(n)，而空間複雜度則縮減為了O(1)。
後記 從官方的題解上看，摩爾投票法被放在了最後，顯然是壓軸的解法（最優解），至於其他諸如暴力、哈希表、排序、隨機化以及分治等解法，大家可以參考下官方題解，從不同方面與摩爾投票法做下對比。
分享到:
