LeetCode每日一题：169.多数元素（二十八）求众数

139 阅读 0 评论 92 点赞

我是靠谱客的博主帅气短靴，这篇文章主要介绍LeetCode每日一题：169.多数元素（二十八）求众数，现在分享给大家，希望可以做个参考。

求众数

一、LeetCode题解

瞧一瞧～

博健的LeetCode题解：Gitbook版本传送门
博健的LeetCode题解：CSDN传送门
有趣的CSS：Gitbook传送门
前端进阶笔记：Gitbook传送门

二、算法题

题目

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。

示例：

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

解法一（Map）

思路

利用Map记录每一个数组出现的次数
返回出现次数最大的值
理论上只需要遍历一次

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var majorityElement = function(nums) {
    var obj = {}
    for(let i = 0; i < nums.length; i++){
        if(obj[nums[i]]){
            obj[nums[i]]++
        }else{
            obj[nums[i]] = 1
        }
    }
    var max = 0, res = nums
    for(var key in obj){
        if(obj[key] > max) {
            max = obj[key]
            res = key
        }
    }
    return res
};

或

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var majorityElement = function(nums) {
    var obj = {}
    var max = nums[0]
    for(let i = 0; i < nums.length; i++){
        if(obj[nums[i]]){
            obj[nums[i]] += 1
            if(obj[max] <= obj[nums[i]]){
                max = nums[i]
            }
        }else{
            obj[nums[i]] = 1
        }
    }
    return max
};

结果

在这里插入图片描述

解法二（排序）

思路

我们假设排序使用快排（时间负责度）= O(nlogn)
如果一个数组被排过序后，出现次数大于 ⌊ n/2 ⌋的一定在数组的中间位置（注意审题，众数的定义）

代码

复制代码

1
2
3
4
5
6
7
var majorityElement = function(nums) {
    nums.sort((a, b)=>{
        return a-b
    })
    return nums[Math.floor(nums.length/2)]
};

结果

在这里插入图片描述

解法三（Boyer-Moore 投票算法）

思路

如果我们把众数记为 +1+1 ，把其他数记为 -1−1 ，将它们全部加起来，显然和大于 0 ，从结果本身我们可以看出众数比其他数多。

算法：

本质上， Boyer-Moore 算法就是找 nums的比拼掉后的值。我们维护一个计数器，如果遇到一个我们目前的候选众数，就将计数器加一，否则减一。只要计数器等于 0 ，我们就将 nums 中之前访问的数字全部忘记，并把下一个数字当做候选的众数。

拿例子举例数组【2，2，1，1，1，2，2】

第一个数2，当前计数器 = 1
第二个数2，当前计数器 = 2
第三个数1，当前计数器 = 1（被对冲掉了一位）
第四个数1，当前计数器 = 0（被对冲掉了一位）
此时计数器为0，前面的被对冲掉了，可以完全忽略
第五个数1，当前计数器 = 1
第六个数2，当前计数器 = 0
此时计数器为0，前面的被对冲掉了，可以完全忽略
第七个数2，当前计数器 = 1，结束，返回当前数字2

因此，上面的过程说明了我们可以放心地遗忘前面的数字，并继续求解剩下数字中的众数。最后，总有一个后缀满足计数器是大于 0 的，此时这个后缀的众数就是整个数组的众数。

总结：`数量 > n/2 的数字可以 1:1对冲掉其他数字，并且还有剩余～`

时间复杂度 O(n)：Boyer-Moore 算法严格执行了 nn 次循环，所以时间复杂度是线性时间的。
空间复杂度 O(1)：Boyer-Moore 只需要常数级别的额外空间。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var majorityElement = function(nums) {
    var idx = null
    var count = 0
    for(let i = 0; i < nums.length; i++){
        if(count ===0 ){
            idx = nums[i]
        }
        if(idx === nums[i]){
            count++
        }else{
            count--
        }
    }
    return idx
};

结果

在这里插入图片描述

最后

以上就是帅气短靴最近收集整理的关于LeetCode每日一题：169.多数元素（二十八）求众数的全部内容，更多相关LeetCode每日一题：169内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：# 汇总：LeetCode题解
浏览次数：139 次浏览
发布日期：2023-12-20 17:00:19
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_2_f1_13__23_g4.html

LeetCode每日一题：169.多数元素（二十八）求众数

求众数

一、LeetCode题解

瞧一瞧～

二、算法题

题目

解法一（Map）

思路

代码

结果

解法二（排序）

思路

代码

结果

解法三（Boyer-Moore 投票算法）

思路

总结：`数量 > n/2 的数字可以 1:1对冲掉其他数字，并且还有剩余～`

代码

结果

最后

评论列表共有 0 条评论

发表评论取消回复

LeetCode每日一题：169.多数元素（二十八）求众数

求众数

一、LeetCode题解

瞧一瞧～

二、算法题

题目

解法一（Map）

思路

代码

结果

解法二（排序）

思路

代码

结果

解法三（Boyer-Moore 投票算法）

思路

总结：数量 > n/2 的数字可以 1:1对冲掉其他数字，并且还有剩余～

代码

结果

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

总结：`数量 > n/2 的数字可以 1:1对冲掉其他数字，并且还有剩余～`

发表评论取消回复