力扣Hot100——169. 多数元素

• 解法1：使用HashMap
  将nums数组映射到HashMap中，键为nums的值，值为nums中值的数量；
  然后遍历哈希表，返回值最大的键
  
  1. class Solution {
  2.     private Map<Integer, Integer> countNums(int[] nums) {
  3.         Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
  4.         for (int num : nums) {
  5.             if (!counts.containsKey(num)) {
  6.                 counts.put(num, 1);
  7.             } else {
  8.                 counts.put(num, counts.get(num) + 1);
  9.             }
  10.         }
  11.         return counts;
  12.     }
  14.         public int majorityElement(int[] nums) {
  15.         Map<Integer, Integer> counts = countNums(nums);
  17.         Map.Entry<Integer, Integer> majorityEntry = null;
  18.         for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
  19.             if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
  20.                 majorityEntry = entry;
  21.             }
  22.         }
  24.         return majorityEntry.getKey();
  25.     }
  26. }

  复制代码
        作者：力扣官方题解
  链接：https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  
• 解法2：由于众数数量凌驾n/2，并且众数一定存在，那么排序后的中心位置的值一定是众数
  
  1. // 排序取中位值
  2. public int majorityElement(int[] nums) {
  3.     Arrays.sort(nums);
  4.     return nums[nums.length/2];
  5. }

  复制代码
• 解法3：Boyer-Moore 投票算法
  起首明白一点：将众数标记为 +1，非众数标记为 -1，遍历所有数值后，众数的和一定是大于零的，由于众数有过半的票数。
  这就像是进行总统推举，我们维护一个总统候选人 candidate ，以及一个 candidate 的票数 count。当遍历选票时，第一次我们将第一张票作为 candidate 的值，然后遍历，碰到雷同的票 count +1，否则 -1，当 count == 0，就将下一张票作为候选人 candidate，如此遍历至末了，candidate 的 count != 0的 candidate一定是票数最多的 candidate，也就是所有票中的众数。（原因就是上面的众数 + 非众数 count 结果一定大于零）
  
  1. class Solution {
  2.        
  3.         public int majorityElement(int[] nums){
  4.                 int candidate = 0;
  5.                 int count = 0;
  6.                
  7.                 for(int num : nums){
  8.                         if(count == 0){
  9.                                 candidate = num;
  10.                         }
  11.                         // 这行代码绝了
  12.                         count +=  (candidate == num) ? +1 : -1;
  13.                 }
  14.                 return candidate;
  15.         }
  16. }

  复制代码
  这行代码绝了！！！count += (candidate == num) ? +1 : -1;
  

关于解法 3 另有一个很好理解的解释，来自于力扣kxACE转发的 youtube 视频，称为同归于尽消杀法
   由于多数凌驾50%, 好比100个数，那么多数至少51个，剩下少数是49个。
遍历数组
   

• 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
  
• 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主稳定，winner 依然是当前这个士兵所属阵营，现存兵力 count 加一；
  
• 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽
  此时前方阵营兵力-1, 即使双方都死光，这块高地的旗帜 winner 稳定，没有可以去换上自己的新旗帜。
  
• 当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。
  就这样各路军阀一直厮杀以一敌一同归于尽的方式下去，直到少数阵营都死光，剩下几个必然属于多数阵营的，winner 是多数阵营。
  

  （多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。