[leetcode]169.多数元素

[MagicalBridge]

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

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

示例 1：

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

示例 2：

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

进阶：

• 尝试设计时间复杂度为 O(n),空间复杂度为O(1)的算法解决此问题

方法一: 哈希表

思路：

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

算法:

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

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  // 创建一个map
  let map = new Map();
  // 循环数组
  for (let i = 0; i < nums.length; i++) {
    // 如果map中不存在这个元素
    if (!map.has(nums[i])) {
      // 给当前这个元素设置为 1
      map.set(nums[i], 1);
    } else {
      // 如果存在了map中，在当前的数量上加1。
      map.set(nums[i], map.get(nums[i]) + 1)
    }
  }

  // 再遍历一遍map 
  for (let [key, value] of map.entries()) {
    // 根据题目条件
    if (value > nums.length / 2) {
      // 返回键名
      return key
    }
  }
};

复杂度：

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