LeetCode 面试题 17.10. Find Majority Element LCCI

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length, freq = (n + 1) / 2, cnt[] = new int[32], ans = 0;
        for (int num : nums)
            for (int i = 0; i <= 31; ++i)
                if ((num >> i & 1) != 0)
                    ++cnt[i];
        for (int i = 0; i <= 31; ++i)
            if (cnt[i] >= freq)
                ans ^= (1 << i);
        for (int num : nums)
            if ((ans ^ num) == 0)
                --freq;
        return freq > 0 ? -1 : ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length, freq = (n + 1) / 2, candidate = 0, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) candidate = num;
            if (num == candidate) ++cnt;
            else --cnt;
        }
        if (cnt <= 0) return -1;
        cnt = 0;
        for (int num : nums)
            if (num == candidate)
                ++cnt;
        return cnt >= freq ? candidate : -1;
    }
}