1. majority element
2. majority element ii

1. Majority Elements

1. after sorted, the middle num must be the majority num
2. boyer-moore algorithm

• if the occurence > length / 2, then the middle number must be the majority number

analysis can be odd num and even num long array

public int majorityElement(int[] nums) {
    if (nums == null || nums.length == 1) return nums[0];
    Arrays.sort(nums);
    //if the occurence > length / 2, then the middle number must be the majority number
    //analysis can be odd num and even num long array
    return nums[nums.length / 2];
}

• boyer-moore algorithm

    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        //先过一遍，当count = 0的时候，设置新的majority
        //当majority == num的时候，count++, else count--;
        int count = 0;
        int majority = 0;
        for (int num: nums) {
            if (count == 0) {
                majority = num;
                count = 1;
            } else {
                if (majority == num) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        //过第二遍，验证下majority是不是真的是 > n / 2
        count = 0;
        for (int num: nums) {
            if (majority == num) {
                count++;
            }
        }
        if (count > nums.length / 2) return majority;
        return -1;
    }

2. Majority Elements II (boyer-moore algorithm)

类似上题，只不过，换了n / 3。所以有可能有1个或者2个数满足这条件。

所以需要两个count, 两个Majority，来判断。

且两个数可能是一样的，所以要判断maj1 == maj2。例子如 [9,9,9,9,9]。

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new LinkedList<Integer>();
        if (nums == null || nums.length == 0) return res;
        int maj1 = 0, maj2 = 0, count1 = 0, count2 = 0;
        for (int num: nums) {
            //这些if else statement的顺序Matters。
            //注意case [8,8,7,7,7]
            if (maj1 == num) {
                count1++;
            } else if (maj2 == num) {
                count2++;
            } else if (count1 == 0) {
                maj1 = num;
                count1++;
            } else if (count2 == 0) {
                maj2 = num;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int num: nums) {
            if (maj1 == num) count1++;
            if (maj2 == num) count2++;
        }
        if (count1 > nums.length / 3) res.add(maj1);
        if (maj1 != maj2 && count2 > nums.length / 3) res.add(maj2);
        return res;
    }