44 - 求众数
题目
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3
示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
解答
首先想到的就是穷举，每个数记录一下出现的次数，然后把最大的数贴出来。
既然有了数组，也可以排序一下，再做计算。
穷举
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function (nums) {
let count = {}
nums.map(e => {
if (e in count) {
count[e]++
} else {
count[e] = 1
}
})
let keys = Object.keys(count)
for (const key of keys) {
if (count[key] > Math.floor(nums.length / 2)) {
return key
}
}
};Runtime: 60 ms, faster than 81.84% of JavaScript online submissions for Majority Element.
Memory Usage: 38 MB, less than 28.57% of JavaScript online submissions for Majority Element.
不知道为啥本地测试环境一直不通过。。明明想要的是3，给的也是3啊。。😂😂
func majorityElement(nums []int) int {
count := make(map[int]int)
for _, elem := range nums {
if _, ok := count[elem]; ok {
count[elem]++
} else {
count[elem] = 1
}
runtime.Gosched()
}
for key, val := range count {
if val > len(nums)/2 {
return key
}
runtime.Gosched()
}
return 0
}Runtime: 44 ms, faster than 5.84% of Go online submissions for Majority Element.
Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Majority Element.
map的定义，是
make(map[int]int)，一开始把struct当成map写了😂判断某元素是否存在，感觉这个
if _, ok:=..的模板很好用map的for遍历，返回的俩数就是
key和value。如果是slice或array，是index和element。
排序
想到排序来化简算法，不过想的也是计算出现最多次数的数字。
其实排序后，只要看一下n/2的数字是哪个，那就是众数了。
var majorityElement = function (nums) {
nums.sort()
if (nums.length % 2 === 0) {
return nums[Math.ceil(nums.length / 2)]
} else {
return nums[Math.floor(nums.length / 2)]
}
};Runtime: 80 ms, faster than 20.69% of JavaScript online submissions for Majority Element.
Memory Usage: 37.4 MB, less than 64.29% of JavaScript online submissions for Majority Element.
func majorityElement(nums []int) int {
sort.Ints(nums)
return nums[len(nums)/2]
}Runtime: 16 ms, faster than 92.69% of Go online submissions forMajority Element.
Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Majority Element.
go很神奇，直接len(nums)/2，都不需要判断奇偶的，就能有正确结果。。
开心消消乐
作者：linxinfu
链接：https://leetcode-cn.com/problems/two-sum/solution/shi-yong-zhan-lai-ji-yi-by-linxinfu/
看到评论取的这个名字，几乎要被笑死😂
做一个栈，如果和栈顶元素一样，就入栈，不一样就出栈。感觉更像是反向的消消乐
换我一百年都想不到这种骚操作😂😂
var majorityElement = function (nums) {
let stack = []
for (const num of nums) {
if (!stack.length) {
stack.push(num)
} else {
const top = stack.pop()
if (top === num) {
stack.push(top)
stack.push(num)
}
}
}
return stack.pop()
};Runtime: 48 ms, faster than 99.71% of JavaScript online submissions for Majority Element.
Memory Usage: 38.3 MB, less than 7.14% of JavaScript online submissions for Majority Element.
go里面似乎没有现成的栈，只能用切片，然后手写相关的操作。
func majorityElement(nums []int) int {
var stack []int
for _, elem := range nums {
if len(stack) == 0 {
stack = append(stack, elem)
} else {
top := stack[len(stack)-1]
stack = stack[0 : len(stack)-1]
if top == elem {
stack = append(stack, top, elem)
}
}
runtime.Gosched()
}
return stack[len(stack)-1]
}Runtime: 28 ms, faster than 18.02% of Go online submissions forMajority Element.
Memory Usage: 6.2 MB, less than 50.00% of Go online submissions forMajority Element.
空切片，似乎只能用var stack []int来定义，tack := []int{}这样goland似乎不推荐。
好像还是用原生的api速度更快，手写的api始终比不上亲生的。。
Boyer-Moore 投票算法
听这名字就感觉很厉害，其实和消消乐差不多。
两个的原理是一样的：众数比其他所有数，都要多。
因此，消消乐是把相同的留下，不同的pop，留下的必然是众数。
这个投票算法，是随机定一个数是众数，同样的就+1，不同的就-1。如果为0，那么定下一个数为众数。
var majorityElement = function (nums) {
let ans = nums[0]
count = 1
for (let i = 1; i < nums.length; i++) {
if (count === 0) {
ans = nums[i]
count++
continue
}
if (nums[i] === ans) {
count++
} else {
count--
}
}
return ans
};Runtime: 60 ms, faster than 81.84% of JavaScript online submissions for Majority Element.
Memory Usage: 37.3 MB, less than 71.43% of JavaScript online submissions for Majority Element.
func majorityElement(nums []int) int {
var (
count int
ans int
)
for _, elem := range nums {
if count == 0 {
ans = elem
count = 1
continue
}
if elem == ans {
count++
} else {
count--
}
runtime.Gosched()
}
return ans
}Runtime: 24 ms, faster than 25.49% of Go online submissions forMajority Element.
Memory Usage: 5.9 MB, less than 50.00% of Go online submissions forMajority Element.
消消乐和算法相比，是拿空间换时间了。不过我更喜欢消消乐的容易理解。
随机
看到了官网的随机解法，没看懂。不过其思想是：众数出现的概率更大
我就想，能不能和消消乐结合一下，随机挑数进栈，玩消消乐。只要最后答案出错的概率很小，那就可以接受不是吗。大不了roll两次，一样了再给答案，不一样再roll一次取一样的值。
那么应该随机多少次呢？首先想到的就是n/2次，也没仔细算过，就觉得本该如此😂
测试环境
发一下抽风的js测试环境。。不知道为啥ans===target也不让过。。
// ======= init ==========
const wrongMsg = (ans, target, index) => {
console.log("😶 wrong:", index);
console.log("* target: ", target);
console.log("* ans: ", ans);
};
const TreeNode = function (val) {
this.val = val;
this.left = this.right = null;
};
function ListNode(val) {
this.val = val;
this.next = null;
}
// ======= code ==========
// =======================
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function (nums) {
let ans = nums[0]
count = 1
for (let i = 1; i < nums.length; i++) {
if (count === 0) {
ans = nums[i]
count++
continue
}
if (nums[i] === ans) {
count++
} else {
count--
}
}
return ans
};
// ======== 测试 ==========
const TEST_DATA = [
// {
// inputs: [3, 2, 3],
// target: 3
// },
// {
// inputs: [2, 2, 1, 1, 1, 2, 2],
// target: 2
// },
// {
// inputs: [1],
// target: 1
// },
// {
// inputs: [2, 2],
// target: 2
// },
{
inputs: [6, 5, 5],
target: 5
},
];
var __main = () => {
for (let i = 0; i < TEST_DATA.length; i++) {
const test = TEST_DATA[i];
// == func ==
const ans = majorityElement(test.inputs)
// ==========
const target = test.target
if (ensure(ans, target, i)) {
return
}
}
console.log("✅✅ all right")
}
const ensure = (ans, target, index) => {
const Ans = (JSON.stringifyans)
const Target = JSON.stringify(target)
if (Ans !== Target) {
wrongMsg(ans, target, index + 1);
return true
}
return false
};
// ==== 主函数 ======
__main()不同以往用web worker来防止死循环，其实只要用node在本地跑，死循环了就ctrl+c退出就完事了，就没那么复杂了。
Last updated
Was this helpful?