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.

Solution1：Moore voting

思路：主要思想是每次找到两个不同的元素 一起弃掉，最终剩下的就是the majority element hat appears more than ⌊ n/2 ⌋ times.
Time Complexity: O(N) Space Complexity: O(1)

Solution1b：Rount1: Moore voting

Time Complexity: O(N) Space Complexity: O(1)

Solution2：Sorting后返回 nums中间元素

思路：主要思想是每次找到两个不同的元素 一起弃掉，最终剩下的就是the majority element hat appears more than ⌊ n/2 ⌋ times.
Time Complexity: O(NlogN) Space Complexity: O(1)

Solution3：Hashmap count

Time Complexity: O(N) Space Complexity: O(N)

Solution4：Divide and Conquer 分治

思路：类似归并排序思想，Divide成左右两部分，分别得到左右部分的Majority Element lm, rm 。Conquer: 在当前序列上分别count lm和rm，作为本level的Majority Element 回传。
Time Complexity: O(NlogN) Space Complexity: O(logN)递归缓存

Solution5：Bit manipulation

思路：32位int，分别统计各位最多次的0or1，因为是> n/2 次，所以一定是结果一定都是majority element的各位，再回组 成结果
Time Complexity: O(N) Space Complexity: O(1)

Solution6：randomly pick

思路：随机选一个 遍历看他是不是Majority element
Time Complexity: O(N^2 with low概率) Space Complexity: O(1)

Solution1 Code：

class Solution {
    // Moore voting algorithm
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == candidate) count++;
            else if(count == 0) {
                candidate = nums[i];
                count = 1;
            }
            else {
                count--;
            }
        }
        return candidate;
    }
}

Solution1b Code：

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

Solution2 Code：

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

Solution3 Code：

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int ret = 0;
        for (int num: nums) {
            if (!map.containsKey(num))
                map.put(num, 1);
            else {
                map.put(num, map.get(num) + 1);
            }
            if(map.get(num) > nums.length / 2) {
                ret = num;
                break;
            }
        }
        return ret;
    }
}

Solution4 Code：

class Solution {
    public int majorityElement(int[] nums) {
        return majority(nums, 0, nums.length - 1);
    }
    
    private int majority(int[] nums, int left, int right) {
        if(left == right) return nums[left];
        int mid = left + (right - left) / 2;
        int lm = majority(nums, left, mid);
        int rm = majority(nums, mid + 1, right);
        
        int majority_num;
        if(count_value(nums, left, right + 1, lm) > count_value(nums, left, right + 1, rm)) {
            majority_num = lm;
        }
        else {
            majority_num = rm;
        }
        return majority_num;
    }
    
    private int count_value(int[] nums, int start, int end, int value) {
        int count = 0;
        for (int i = start; i < end; i++) {
            if (nums[i] == value) count ++;
        }
        return count;
    }
    
}

Solution5 Code：

class Solution {
    // Bit manipulation 
    public int majorityElement(int[] nums) {
        int[] bit = new int[32];
        for (int num: nums) {
            for (int i = 0; i < 32; i++) {
                if ((num >> (31 - i) & 1) == 1) {
                    bit[i]++;
                }
            }
        }
        
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            bit[i] = bit[i] > nums.length / 2 ? 1 : 0;
            ret += bit[i] * (1 << (31 - i));
        }
        return ret;
    }
}