169. Majority Element

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.

Solution:

cancel each pair of different numbers. If there is a majority number, it will have more than one left.

    public int majorityElement(int[] nums) {
        int m = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                m = nums[i];
                count = 1;
            } else if (nums[i] != m) {
                count--;
            } else {
                count++;
            }
        }
        return m;
    }

Solution 2: Using bit manipulation.

Sum up all 1s at each bit and save them to bit[32]. If bit[i] > nums.length/2, this bit of result is 1, otherwise 0.

    public int majorityElement(int[] nums) {
        int[] bit = new int[32];
        for (int num : nums) {
            for (int i = 0; i <= 31; i++) {
                if ((num&(1<<i)) != 0) {
                    bit[i]++;
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= 31; i++) {
            if (bit[i] > nums.length/2) {
                res |= 1<<i;
            }
        }
        return res;
    }

Other ways not preferred:

1. sort the array, and return the nums[nums.length/2];
2. using hashmap to count the number of appearances, and return the number appears most.