Skip to main content

169. Majority Element

分析

排序的方法就不说了

提一下 题目中这个 大于 n / 2 的设定, 好好利用这一点
用类似抵消的方案可以在 时间 O(n) 空间 O(1) 的资源下解决

题解

排序方案

function majorityElement(nums: number[]): number {
nums.sort((a, b) => a - b)
let cnt = 1
let halfLen = Math.floor(nums.length / 2)
let prev = nums[0]
for (const num of nums.slice(1)) {
if (num === prev) {
cnt++

if (cnt > halfLen) {
return num
}
continue
}
prev = num
}

return prev
};

抵消方案

function majorityElement(nums: number[]): number {
let cnt = 1
let ans = nums[0]
for (let i = 1; i < nums.length; i++) {
const num = nums[i]
if (num === ans) {
cnt++
continue
}
cnt--
if (cnt === 0) {
ans = num
cnt = 1
}
}

return ans
};