【算法-LeetCode】169. 多数元素（Map）169. 多数元素 - 力扣（LeetCode）

74 阅读 0 评论 49 点赞

我是靠谱客的博主缥缈过客，这篇文章主要介绍【算法-LeetCode】169. 多数元素（Map）169. 多数元素 - 力扣（LeetCode），现在分享给大家，希望可以做个参考。

169. 多数元素 - 力扣（LeetCode）

发布：2021年10月10日20:15:49

问题描述及示例

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解（Map）

总体思路是设置一个目标数量为 half = Math.ceil(nums.length / 2)，并用一个 Map 类型的结构 map 来存储 nums 中的数字与其出现次数的映射关系。其中数字为 key，而其出现次数为对应的 value。

遍历 nums 数组，并检查当前元素是否已经在 map 中，

如果不在，则将当前元素存入 map 中，并设置其值为 1。
如果已经存在，则将其 value 在原来的基础上加一。

在将当前元素放入 map 前，如果发现将当前元素放入 map 后，其数量就能达到 half，则可以立即返回当前元素。

在这里插入图片描述

没有考虑到数组中只有两个相等元素的情况

详解请看下方注释：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  // 如果nums中的元素数量不超过2，则将第一个元素返回即可
  if(nums.length <= 2) {
    return nums[0];
  }
  // map用来存储数字与其数量的映射关系
  let map = new Map();
  // half 是达标的数量，一旦某个数字的数量达到half，则该数字就为多数元素
  let half = Math.ceil(nums.length / 2);
  // 开始遍历nums
  for(let num of nums) {
    // 如果发现将当前元素放入map后可以达标，那么就可以直接将当前元素返回
    if(map.get(num)+1 === half) {
      return num;
    }
    // 如果map中已经有当前元素，则将其数量在原来基础上加1，否则将其加入map，并设置数量为1
    map.has(num) ? map.set(num, map.get(num) + 1) : map.set(num, 1);
  }
};

提交记录
47 / 47 个通过测试用例
状态：通过
执行用时：68 ms, 在所有 JavaScript 提交中击败了92.17%的用户
内存消耗：41.2 MB, 在所有 JavaScript 提交中击败了50.37%的用户
时间：2021/10/10 20:17