[leetcode]229.求众数II

[MagicalBridge]

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

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

示例 1：

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

示例 2：

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

示例 3：

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

方法一: 哈希表

思路：

我们知道出现次数最多的元素大于 [n/3]次，所以可以使用哈希表来快速统计每个元素出现的次数。

算法:

我们使用哈希映射来存储每个元素以及出现的次数，对于哈希表中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组nums,并将数组中的每个元素加入hash映射中，在这之后，我们遍历哈希映射中的所有键值对，返回最大值的键，我们同样也可以在遍历数组nums时候用打擂台的方法，维护最大的值，这样省去了最后对hash映射的遍历。

这道题目可以看成是169题目的进阶版本，这道题目的返回值要求输出所有符合的值，我们想到需要一个数组来维护结果。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function (nums) {
  let map = new Map();

  for (let i = 0; i < nums.length; i++) {
    if (!map.has(nums[i])) {
      map.set(nums[i], 1);
    } else {
      map.set(nums[i], map.get(nums[i]) + 1);
    }
  }
  let resArr = []
  for (let [key, value] of map.entries()) {
    if (value > nums.length / 3) {
      resArr.push(key);
    }
  }
  return resArr
};

复杂度：

• 时间复杂度O(n)
• 空间复杂度O(n)