劍指 Offer 39. 數組中出現次數超過一半的數字
劍指 Offer 39. 數組中出現次數超過一半的數字
數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。
你可以假設數組是非空的，並且給定的數組總是存在多數元素。
示例 1:
輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2
限制：
1 <= 數組長度 <= 50000
一、摩爾演算法
具體摩爾演算法，我借鑒一下大神的解釋更好理解點。
為什麼答案能寫那麼長呢。。。核心就是對拼消耗。玩一個諸侯爭霸的遊戲，假設你方人口超過總人口一半以上，並且能保證每個人口出去干仗都能一對一同歸於盡。最後還有人活下來的國家就是勝利。那就大混戰唄，最差所有人都聯合起來對付你（對應你每次選擇作為計數器的數都是眾數），或者其他國家也會相互攻擊（會選擇其他數作為計數器的數），但是只要你們不要內鬥，最後肯定你贏。最後能剩下的必定是自己人。
class Solution {
public int majorityElement(int[] nums) {
int vote = 0, x = 0;
for (int num : nums) {
if (vote == 0) x =num;
vote += num == x ? 1 : -1;
}
return x;
}
/*
x=num=1
vote=1
x = 2
vote = 0
x =3 vote=1
vote = 0
x = num =2 vote =1
*/
}
除了這個，由於題目要求給定的數組總是存在多數元素，所以需要加入「驗證環節」，所以借鑒了K神的思路，遍曆數組統計x的量，如果大於num.length/2，則x是眾數，否則反正。
class Solution {
public int majorityElement(int[] nums) {
int vote = 0, x = 0, count = 0;
for (int num : nums) {
if (vote == 0) x =num;
vote += num == x ? 1 : -1;
}
for (int num : nums)
if (num == x) count++;
return count > nums.length/2 ? x : 0;
}
}
二、哈希
class Solution {
/*
用HashMap統計num的數量，即可找出眾數
*/
public Map<Integer,Integer> map(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num,map.get(num) + 1);
}
}
return map;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = map(nums);
Map.Entry<Integer,Integer> majorityElement = null;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (majorityElement == null || entry.getValue() > majorityElement.getValue()) {
majorityElement = entry;
}
}
return majorityElement.getKey();
}
}
三、數組排序
class Solution {
/*
用數組nums進行排序
*/
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
參考鏈接：
1）//www.zhihu.com/question/49973163/answer/617122734
2）劍指 Offer 39. 數組中出現次數超過一半的數字（摩爾投票法，清晰圖解） – 數組中出現次數超過一半的數字 – 力扣（LeetCode） (leetcode-cn.com)
