229.多数元素II

链接：229.多数元素II
难度：Medium
标签：数组、哈希表、计数、排序
简介：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

题解 1 - typescript

• 编辑时间：2021-10-22
• 执行用时：88ms
• 内存消耗：41.8MB
• 编程语言：typescript
• 解法介绍：哈希存储。

function majorityElement(nums: number[]): number[] {
  const map = new Map<number, number>();
  const n = nums.length;
  for (const num of nums) {
    map.set(num, (map.get(num) ?? 0) + 1);
  }
  return Array.from(map.entries())
    .filter(([, v]) => v > n / 3)
    .map(([k]) => k);
}

题解 2 - typescript

• 编辑时间：2021-10-22
• 执行用时：88ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：摩尔投票，超过 n/3 的数最多有 2 个，每三个不同的数进行抵消。

function majorityElement(nums: number[]): number[] {
  const n = nums.length;
  let num1 = nums[0];
  let num2 = nums[0];
  let val1 = 0;
  let val2 = 0;
  for (const num of nums) {
    if (val1 > 0 && num === num1) {
      val1++;
    } else if (val2 > 0 && num === num2) {
      val2++;
    } else if (val1 === 0) {
      num1 = num;
      val1++;
    } else if (val2 === 0) {
      num2 = num;
      val2++;
    } else {
      val1--;
      val2--;
    }
  }
  let cnt1 = 0;
  let cnt2 = 0;
  for (const num of nums) {
    if (val1 > 0 && num1 === num) cnt1++;
    if (val2 > 0 && num2 === num) cnt2++;
  }
  const ans: number[] = [];
  if (val1 > 0 && cnt1 > n / 3) ans.push(num1);
  if (val2 > 0 && cnt2 > n / 3) ans.push(num2);
  return ans;
}

题解 3 - cpp

• 编辑时间：2022-01-07
• 执行用时：12ms
• 内存消耗：15.4MB
• 编程语言：cpp
• 解法介绍：最多只可能有两个数，声明两个变量记录数值和次数，遍历时相互抵消。

class Solution {
   public:
    vector<int> majorityElement(vector<int> &nums) {
        int cnt1 = 0, num1, cnt2 = 0, num2;
        for (auto &num : nums) {
            if ((cnt1 == 0 || num1 == num) && num2 != num)
                num1 = num, cnt1++;
            else if (cnt2 == 0 || num2 == num)
                num2 = num, cnt2++;
            else
                cnt1--, cnt2--;
        }
        cnt1 = cnt2 = 0;
        for (auto &num : nums) {
            if (num1 == num)
                cnt1++;
            else if (num2 == num)
                cnt2++;
        }
        vector<int> ans;
        if (cnt1 * 3 > nums.size()) ans.push_back(num1);
        if (cnt2 * 3 > nums.size()) ans.push_back(num2);
        return ans;
    }
};