javascript-leetcode
javascript-leetcode copied to clipboard
169. 多数元素
摩尔投票算法
摩尔投票算法有点“天天爱消除”的感觉,证明过程详见官方题解。
先明确,所谓多数元素就是该元素的个数超过数组长度的一半。
所以我们可以让不同的数字相互抵消,最后剩下的数字就是多数元素。
const majorityElement = function(nums) {
let target = 0
let count = 0
for (let i = 0; i < nums.length; i++) {
if (count === 0) {
target = nums[i]
}
if (nums[i] === target) {
count++
} else {
count--
}
}
return target
}
- 时间复杂度: O(n)
- 空间复杂度: O(1)
var majorityElement = function (nums) {
const n = nums.length
let map = new Map()
for (let i = 0; i < n; i++) {
if (map.has(nums[i])) {
map.set(nums[i], map.get(nums[i]) + 1)
} else {
map.set(nums[i], 1)
}
}
for (let j = 0; j < n; j++) {
if (map.get(nums[j]) > n / 2) {
return nums[j]
}
}
};