169 - 求众数(majority-element)

Create by jsliang on 2019-07-05 13:54:05
Recently revised in 2019-07-05 14:48:53

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - Map()

二 前言

返回目录

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

你可以假设数组是非空的,并且给定的数组总是存在众数。

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

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

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - Map()

返回目录

  • 解题代码
var majorityElement = function(nums) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.get(nums[i]) !== undefined) {
      map.set(nums[i], map.get(nums[i]) + 1);
      if (map.get(nums[i]) > nums.length / 2) {
        return nums[i];
      }
    } else {
      map.set(nums[i], 1);
      if (map.get(nums[i]) > nums.length / 2) {
        return nums[i];
      }
    }
  }
};
  • 执行测试

  • nums[2,2,1,1,1,2,2]

  • return2

  • LeetCode Submit

✔ Accepted
  ✔ 44/44 cases passed (96 ms)
  ✔ Your runtime beats 83.27 % of javascript submissions
  ✔ Your memory usage beats 24.14 % of javascript submissions (37.7 MB)
  • 知识点

  • Map:保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。Map 详细介绍

  • 解题思路

首先Map() 作为一个 有记忆功能Object,在 LeetCode 中经常以哈希算法的形式出现,是个非常实用的 API,小伙伴们可以尝试多使用几次,记住 Map() 的使用技巧。

然后jsliang 讲讲使用 Map() 的解题思路:

  1. 通过 for() 遍历一遍 nums
  2. 判断 nums 中的每个元素,如果在 Map() 中有存在,则将其出现次数 + 1,如果它的出现次数已经超过 nums.length / 2,那么它就是众数。
  3. 然后,如果它没在 Map() 中存在,那么就直接存为 1,同时给个判断是否出现次数超过 nums.length / 2,这是预防如果数组为 [1] 的情况。

这样,我们就完成了这道题的破解。

  • 进一步思考

除了 Map(),可能还有其他方法,这就需要小伙伴们去探索啦~


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-05 14:48:53

results matching ""

    No results matching ""