问题描述

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

思路

最简单的方法就是哈希表统计每个元素的出现次数。但是，假设元素个数非常多，那么内存的浪费也会很可观。

而使用摩尔投票法，可以实现时间复杂度为 O (n)、空间复杂度为 O (1) 。

代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majEle = -INT_MAX, majCounter = 1, i = 0;
        while(i < nums.size()){
            if(nums[i] != majEle)
                majCounter -= 1;
            else
                majCounter ++;
            if(majCounter == 0){
                majEle = nums[i];
                majCounter = 1;
            }
            i++;
        }
        return majEle;
    }
};

How it works?

摩尔投票法利用的是 “抵消” 的思想。每遇到一个不同元素，计数器 - 1。如果计数归零，就将主导权交给遇到的那个元素。我们从一个例子入手说明。

假设输入：

2 2 1 1 1 2 2

nums:  2 2 1 1 1 2 2
       ^
count: 1
major: 2

nums:  2 2 1 1 1 2 2
         ^
count:   2
major:   2

nums:  2 2 1 1 1 2 2
           ^
count:     1 （遇到不同，count--）
major:     2

nums:  2 2 1 1 1 2 2
             ^
count:       0 （遇到不同，count--）
major:       2

nums:  2 2 1 1 1 2 2
             ^
count:       1 （count 归零，主导权交出）
major:       1

nums:  2 2 1 1 1 2 2
               ^
count:         2
major:         1

nums:  2 2 1 1 1 2 2
                 ^
count:           1
major:           1

nums:  2 2 1 1 1 2 2
                   ^
count:             0（遇到不同，count--）
major:             1

nums:  2 2 1 1 1 2 2
                   ^
count:             1
major:             2 （count 归零，主导权交出）

核心思想：抵消

我们可以换一个角度看问题：

nums:  2 2 1 1 1 2 2
         [ ]
         抵消 2 1
         
nums:    2 1 1 2 2
         [ ]
         抵消 2 1
         
nums:  1 2 2
       [ ] 
       抵消 1 2
       
nums:  2
      赢家

无论多苛刻的输入，都能解决！

nums: 1 2 9 9 8 9 7 7 9 9
      ^
      maj = 1, cnt = 1

nums: 1 2 9 9 8 9 7 7 9 9
      x x
          maj = 2, cnt = 1

nums: 1 2 9 9 8 9 7 7 9 9
      x x ^
          maj = 9, cnt = 1
          
nums: 1 2 9 9 8 9 7 7 9 9
      x x   ^
          maj = 9, cnt = 2
          
nums: 1 2 9 9 8 9 7 7 9 9
      x x x   x
          maj = 9, cnt = 1（注意，抵消 8 9）

nums: 1 2 9 9 8 9 7 7 9 9
      x x x   x ^
          maj = 9, cnt = 2

nums: 1 2 9 9 8 9 7 7 9 9
      x x x x x x x
          maj = 9, cnt = 1

nums: 1 2 9 9 8 9 7 7 9 9
      x x x x x x x x
          maj = 7, cnt = 1
          
nums: 1 2 9 9 8 9 7 7 9 9
      x x x x x x x x ^
          maj = 9, cnt = 1
          
nums: 1 2 9 9 8 9 7 7 9 9
      x x x x x x x x   ^
          maj = 9, cnt = 2          
赢家出现！

什么情况下不能用？

注意必须保证元素出现次数 $> n/2$，这种情况下才能保证统计正确。并不能而非出现次数最多的。

比如上面的数组前缀 1 2 9 9 8 9 7 7 （删掉末尾两个 9），将会统计出 7，是错误的答案。

进阶：求 n/3 众数

229. 求众数 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

分析

这题两个变化：

  1. 频次限制 $> n /3$
  2. 需要找出具体的元素。

从数学原理上，出现超过 ⌊ n/3 ⌋ 次的元素，最多只能有两个。因此可以分别计数。

解题原理

对两个超过 ⌊ n/3 ⌋ 次的元素分别分配计数变量。初始化都指向 nums [0], cnt 都是 0.

开始遍历。对当前元素，分类讨论：

  • 如果当前元素是两个中的一个，则对应计数增加。
  • 否则将两个的计数抵消掉 1.
  • 如果任何一个计数归零，说明它的频次不可能达到 ⌊ n/3 ⌋ 次，将其炒鱿鱼，换成当前元素。

代码实现


class Solution {
public:
  vector<int> majorityElement(vector<int> &nums) {
    auto n = nums.size();
    vector<int> ret;
    if (n == 0) {
      return ret;
    }
    auto n1 = nums[0], c1 = 0;
    auto n2 = nums [0], c2 = 0; // 注意两个都初始化为 nums [0]

    for (unsigned i = 0; i < n; ++i) { // 注意从 i = 0 开始
      auto num = nums[i];
      if (num == n1) {
        c1++;
        continue;
      }
      if (num == n2) {
        c2++;
        continue;
      }
      if (c1 == 0) {
        n1 = num;
        c1++;
        continue;
      }
      if (c2 == 0) {
        n2 = num;
        c2++;
        continue;
      }
      c1--;
      c2--;
    }

    // statistics
    c1 = 0;
    c2 = 0;

    // 会不会出现 n1 = n2?
    for (unsigned i = 0; i < n; ++i) {
      if (nums[i] == n1) {
        c1++;
      } else if (nums [i] == n2) { // 注意这里是 else if
        c2++;
      }
    }
    if (c1 > n / 3) {
      ret.push_back(n1);
    }
    if (c2 > n / 3) {
      ret.push_back(n2);
    }
    return ret;
  }
};

执行过程：

nums = { 7, 7, 9, 8, 9, 7, 7, 9, 9 }
ele = 7  ele1, cnt1 = 7, 1  ele2, cnt2 = 7, 0
ele = 7  ele1, cnt1 = 7, 2  ele2, cnt2 = 7, 0
ele = 9  ele1, cnt1 = 7, 2  ele2, cnt2 = 9, 1
ele = 8  ele1, cnt1 = 7, 1  ele2, cnt2 = 9, 0
ele = 9  ele1, cnt1 = 7, 1  ele2, cnt2 = 9, 1
ele = 7  ele1, cnt1 = 7, 2  ele2, cnt2 = 9, 1
ele = 7  ele1, cnt1 = 7, 3  ele2, cnt2 = 9, 1
ele = 9  ele1, cnt1 = 7, 3  ele2, cnt2 = 9, 2
ele = 9  ele1, cnt1 = 7, 3  ele2, cnt2 = 9, 3