169. Majority Element

数组中超过一半的数字

1.Boyer-Moore majority vote algorithm

O(n) + O(1)

public static int majorityElement(int[] nums) {
    int major = 0, count = 0;
    for (int n: nums) {
        if (count == 0) {
            count++;
            major = n;
        } else if (major == n)  {
            count++;
        } else {
            count--;
        }
    }

    // verify
    int c = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] == major) c++;
    }
    return (c > array.length / 2) ? major : 0;
}

粉色格子为count=0时换主，返回绿色格子

2.字典

O(n) + O(n)

public int majorityElement3(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (Integer n : nums) {
        if (map.containsKey(n)) {
            map.put(n, map.get(n) + 1);
        } else {
            map.put(n, 1);
        }
        if (map.get(n) > nums.length / 2) {
            return n;
        }
    }
    return 0;
}

3.排序+返回中间值

O(nlogn) + 大概是O(logn)?

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

Ref

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html