LeetCode 169. Majority Element
LeetCode 169. Majority Element
題目描述
思路1 Hash表
很直接,程式碼略
由於題目的follow-up要求空間複雜度O(1),所以,這個方法其實並不是最優解。
思路2 一次刪除兩個不同的數
一次刪除兩個不同的數,如果存在majority element,那麼這個majority element一定會最後剩下來,但是,不能說一次刪除兩個不同的數,最後剩下了來的數就是majority element,比如{1,2,3,4,5} 這個數組,最後剩下5,5不是要求的值。所以,在執行完每次刪除兩個不同的數這個操作後,最後留下的數,還要過一遍數組,看下這個數是不是超過了半數,如果超過半數,才算是最後結果。程式碼見:
public static int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
if (nums.length == 1) {
return nums[0];
}
int cand = nums[0];
int HP = 1;
int i = 1;
int limit = nums.length >> 1;
while (i < nums.length) {
if (cand == nums[i]) {
HP++;
// 如果某時,HP已經大於一半的數了,直接返回
if (HP > limit) {
return nums[i];
}
} else {
if (HP == 0) {
cand = nums[i];
HP++;
} else {
HP--;
}
}
i++;
}
if (HP == 0) {
return -1;
}
int c = 0;
for (int num : nums) {
if (cand == num) {
c++;
}
}
if (c > limit) {
return cand;
} else {
return -1;
}
}
說明:
其中HP標識候選數出現的次數,我們可以假設侯選數一開始就是num[0],只要遍歷到的數和候選數一致,HP++,不一致,直接HP歸零,侯選數置為當前數,這樣就實現了一次刪除兩個數的目的。
此外,這裡有一個小的貪心,就是當HP已經到達數組一半以上的大小時候,直接返回當前的候選數(因為HP就表示侯選數出現的次數)