Majority Element（求大多数）

https://leetcode.com/problems/majority-element/
给定一个int 数组，找出这个数组中超过一半的数字（You may assume that the array is non-empty and the majority element always exist in the array.）

• 方法一 hashmap搞定， 时间O(n),空间O(n)

public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        if(nums.length <= 0){
            return -1;
        }

        for (int i = 0; i < nums.length; i++) {
            int tmp = nums[i];
            if (hash.containsKey(tmp)) {
                int cnt = hash.get(tmp);
                if (cnt + 1 >= nums.length / 2) {
                    return tmp;
                }
                hash.put(tmp, cnt + 1);
            } else {
                hash.put(tmp, 0);
            }
        }
        return nums[0];
    }

• 方法二 Moore Voting 摩尔投票法则
  从开始遍历nums中的每一个num
  • 从第一个开始假定nums[0]就是我们要找的过半的值
  • 继续找到第二个，如果nums[1]等于nums[0]，则cnt++， 否则cnt--
  • 循环迭代前面两个步骤
  • 当cnt等于0 的情况下，把当前的nums[i]再假象成过半的int，继续迭代

 public int majorityElement2(int[] nums) {
        int res = 0, cnt = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (cnt == 0) {
                res = num;
                ++cnt;
            } else {
                cnt = num == res ? cnt + 1 : cnt - 1;
            }
        }
        return res;
    }

https://leetcode.com/problems/majority-element-ii/
求大多数的升级版，给定一个int数组，长度为n，找出长度超过n/3的所有int

题目要求只能用O(1)的存储空间，所以排除HashMap的方法目前只能摩尔投票法则

• 长度超过n/3的所有数字，最多存在两个
• 类比找n/2的方法，所以假设有两个int，
• 本题没有说一定存在这两个int，所以在找到后一定要证明这两个int一定是超过n/3的
• 综上所述，这个方法是需要遍历两遍数组，同时空间复杂度为O(1)

 public List<Integer> majorityElement3(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        //假装 a 和b两个int就是最后要找到的两个整数
        //cnt1和cnt2分别代表a和b出现的次数
        int a = 0, b = 0, cnt1 = 0, cnt2 = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            
            //每次遍历到的整数等于a，则对应的cnt1加1
            if (num == a) {
                cnt1++;
            } else if (num == b) {
                cnt2++;
            } else if (cnt1 == 0) {
                a = num;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                b = num;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        cnt1 = cnt2 = 0;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == a) {
                cnt1++;
            } else if (num == b) {
                cnt2++;
            }
        }

        if (cnt1 > n / 3) {
            res.add(a);
        }

        if (cnt2 > n / 3) {
            res.add(b);
        }
        return res;
    }