从零学算法169

169.给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

• 我的原始人解法：hash 表计数，大于就 return

•   public int majorityElement(int[] nums) {
        int max = nums.length / 2;
        Map<Integer,Integer> map = new HashMap<>();
        for(int n:nums){
            int count = map.getOrDefault(n,0);
            if(count >= max) return n;
            map.put(n,count+1);
        }
        return 0;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 他人解法1：由于众数数量大于 数组长度 / 2，所以排序后的数组，中点元素必为众数

•   public int inventoryManagement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
  1
  2
  3
  4

• 他人解法2：摩尔投票法，由于众数的数目多余其他数，所以如果把众数记作 1，其他数记作 -1，最后的和一定大于 0
• 并且，我们在相加的过程中，只要遇到票数为 0，就说明之前的票数已经两两抵消了，你可以看做众数的兵力一定比其他数充足，并且两方的兵实力相当，能以一换一，双方不断派出兵，票数为 0 说明换了一轮血，双方各自阵亡了同等数目的兵力，你会发现，只要一直这样争斗下去，最后一定是只剩众数那一方的人了。
• 根据这个思路，我们可以先假设数组中的任意一个数为众数，只要他是真的众数，哪怕他在某一轮争斗阵亡（发生票数和为 0），他的兄弟还是会替他顶上，而只要他不是真的众数，他最终一定会被众数消灭。

•   public int inventoryManagement(int[] nums) {
    	// ans：众数
    	// votes： 当前票数和
        int ans = 0, votes = 0;
        for(int n:nums){
        	// 真金不怕火炼，双方阵亡一次我就先当做当前的 n 为众数好了
            if(votes == 0)ans=n;
            // 双方派兵，直到两方人数相等就又会在上面更新 ans
            votes += n==ans ? 1 : -1;
        }
        return ans;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12