多数元素

题面

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

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

示例 1：

输入： nums = [3,2,3] 输出： 3

示例 2：

输入： nums = [2,2,1,1,1,2,2] 输出： 2

提示：

• n == nums.length 1 <= n <= 5 104
• -109 <= nums[i] <= 109
• 输入保证数组中一定有一个多数元素。

进阶： 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

分析

• 题意：计算 nums 的严格众数；严格众数的出现次数，比其余所有元素的出现次数加起来还多

• 尝试设计一个 $\mathcal{O}(n)$ 一次遍历，同时只用到 $\mathcal{O}(1)$ 额外空间的算法

• 想象一众武林高手比武，谁会笑到最后？用「擂台赛」打比方：

  • 擂主登场：nums[0] 成为初始擂主，生命值为 1
  • 挑战者出现：遍历后续元素，作为挑战者
  • 比武：如果挑战者与擂主属于同一门派（值相同），那么擂主生命值加 1，否则擂主生命值减 1
  • 擂主更迭：如果比武后，擂主生命值降为 0（同归于尽），那么下一个挑战者成为新的擂主，生命值为 1
  • 最后在擂台上的那人，便是武林盟主（严格众数）

• 为什么这样做是对的？设出现次数最多的元素的出现次数为 $a$，其余元素的出现次数之和为 $b = n - a$。题目保证 $a > b$

• 证明：上述过程中，每次擂主的生命值降为 0 时，相当于开了一个新的擂台赛，在 nums[i] 和 nums[i+1] 之间切一刀，这会把 nums 分成若干段。依次考察这些段：

  • 对于除了最后一段的每一段，设严格众数在其中出现了 $x$ 次，其余元素的出现次数之和为 $y$，必然有 $x \le y$。这可以用反证法证明，如果 $x > y$，那么严格众数血多，不可能被其余元素同归于尽，严格众数的生命值在这段结束时必然大于 0，矛盾。由此可得 $a - x > b - y$，意思是，把 $a$ 减去 $x$，$b$ 减去 $y$，所得到的 $a'$ 和 $b'$ 仍然满足 $a' > b'$。依此类推，每一段结束时，在剩余元素（未遍历到的元素）中，设出现次数最多的元素的出现次数为 $a'$，其余元素的出现次数之和为 $b'$，那么 $a' > b'$ 始终成立
  • 对于最后一段，由于 $a' > b'$​，严格众数血多，不可能被其余元素同归于尽，严格众数的生命值最终必然大于 0，所以最后在擂台上的是严格众数

• 这就是摩尔投票法的思路

  • 候选人(cand_num)初始化为 nums[0]，票数 count 初始化为 1
  • 当遇到与 cand_num 相同的数，则票数 count = count + 1，否则票数 count = count - 1
  • 当票数 count 为 0 时，更换候选人，并将票数 count 重置为 1
  • 遍历完数组后，cand_num 即为最终答案

• 在任何数组中，出现次数大于该数组长度一半的值只能有一个

• 代码实现

  class Solution {
  public:
      int majorityElement(vector<int>& nums) {
          int max = -1;
          int cnt = 0;
          for (int i = 0; i < nums.size(); i++) {
              if (max == nums[i])
                  cnt++;
              else if (--cnt < 0) {
                  max = nums[i];
                  cnt++;
              }
          }
          return max;
      }
  };

多数元素 II

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

• 摩尔投票法可以改进用于 1/3 场景，在任何数组中，出现次数大于该数组长度1/3的值最多只有两个

• 代码如下

  class Solution {
  public:
      vector<int> majorityElement(vector<int>& nums) {
          vector<int> ans;
          int element1 = 0;
          int element2 = 0;
          int vote1 = 0;
          int vote2 = 0;
  
          for (auto & num : nums) {
              if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
                  vote1++;
              } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
                  vote2++;
              } else if (vote1 == 0) { // 选择第一个元素
                  element1 = num;
                  vote1++;
              } else if (vote2 == 0) { // 选择第二个元素
                  element2 = num;
                  vote2++;
              } else { //如果三个元素均不相同，则相互抵消1次
                  vote1--;
                  vote2--;
              }
          }
  
          int cnt1 = 0;
          int cnt2 = 0;
          for (auto & num : nums) {
              if (vote1 > 0 && num == element1) {
                  cnt1++;
              }
              if (vote2 > 0 && num == element2) {
                  cnt2++;
              }
          }
          // 检测元素出现的次数是否满足要求
          if (vote1 > 0 && cnt1 > nums.size() / 3) {
              ans.push_back(element1);
          }
          if (vote2 > 0 && cnt2 > nums.size() / 3) {
              ans.push_back(element2);
          }
  
          return ans;
      }
  };