169. Majority Element (E)

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊n/2⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

题意

找到数组中出现次数超过一半的元素。

思路

1. 直接用HashMap记录每一个元素出现的次数；
2. 先将数组排序，则此时数组的中位数就是要求的元素x(因为x出现次数大于n/2)；
3. 位运算，统计所有数字每一位上1和0的个数，则目标数字x对应位上的值是其中个数较多的那一个；
4. Boyer-Moore Majority Vote

代码实现 - Hash

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) > nums.length / 2) {
                return x;
            }
        }
        return 0;
    }
}

代码实现 - 排序

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

代码实现 - 位运算

class Solution {
    public int majorityElement(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int ones = 0, zeros = 0;
            for (int num : nums) {
                if (ones > nums.length/2 || zeros > nums.length / 2) break;
                if ((num & (1 << i)) != 0) ones++;
                else zeros++;
            }
            if (ones > zeros) {
                ans = ans | (1 << i);
            }
        }
        return ans;
    }
}

代码实现 - Boyer-Moore Majority Vote

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int ans = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                ans = nums[i];
                count++;
            } else {
                count += nums[i] == ans ? 1 : -1;        
            }
        }
        return ans;
    }
}