0229. 多数元素 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 摩尔投票法

1. 📝 题目描述

• leetcode

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

示例 1：

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

示例 2：

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

示例 3：

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

---

提示：

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

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

2. 🎯 s.1 - 摩尔投票法

c

int* majorityElement(int* nums, int numsSize, int* returnSize) {
    int c1 = 0, c2 = 0, cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < numsSize; i++) {
        if (cnt1 > 0 && nums[i] == c1) cnt1++;
        else if (cnt2 > 0 && nums[i] == c2) cnt2++;
        else if (cnt1 == 0) { c1 = nums[i]; cnt1 = 1; }
        else if (cnt2 == 0) { c2 = nums[i]; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    cnt1 = 0; cnt2 = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == c1) cnt1++;
        else if (nums[i] == c2) cnt2++;
    }
    int* res = (int*)malloc(sizeof(int) * 2);
    *returnSize = 0;
    if (cnt1 > numsSize / 3) res[(*returnSize)++] = c1;
    if (cnt2 > numsSize / 3) res[(*returnSize)++] = c2;
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function (nums) {
  let c1 = 0,
    c2 = 0,
    cnt1 = 0,
    cnt2 = 0
  for (const num of nums) {
    if (cnt1 > 0 && num === c1) cnt1++
    else if (cnt2 > 0 && num === c2) cnt2++
    else if (cnt1 === 0) {
      c1 = num
      cnt1 = 1
    } else if (cnt2 === 0) {
      c2 = num
      cnt2 = 1
    } else {
      cnt1--
      cnt2--
    }
  }
  // 验证
  cnt1 = 0
  cnt2 = 0
  for (const num of nums) {
    if (num === c1) cnt1++
    else if (num === c2) cnt2++
  }
  const res = []
  if (cnt1 > nums.length / 3) res.push(c1)
  if (cnt2 > nums.length / 3) res.push(c2)
  return res
}

py

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        c1 = c2 = 0
        cnt1 = cnt2 = 0
        for num in nums:
            if cnt1 > 0 and num == c1:
                cnt1 += 1
            elif cnt2 > 0 and num == c2:
                cnt2 += 1
            elif cnt1 == 0:
                c1, cnt1 = num, 1
            elif cnt2 == 0:
                c2, cnt2 = num, 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        cnt1 = sum(1 for x in nums if x == c1)
        cnt2 = sum(1 for x in nums if x == c2)
        res = []
        if cnt1 > len(nums) // 3:
            res.append(c1)
        if cnt2 > len(nums) // 3:
            res.append(c2)
        return res

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 超过 $\lfloor n/3\rfloor$ 的元素最多两个，维护两个候选人及其计数
• 第一次遍历找候选人，第二次遍历验证候选人是否真正超过阈值