javascript-leetcode icon indicating copy to clipboard operation
javascript-leetcode copied to clipboard

169. 多数元素

Open Geekhyt opened this issue 4 years ago • 1 comments

原题链接

摩尔投票算法

摩尔投票算法有点“天天爱消除”的感觉,证明过程详见官方题解。

先明确,所谓多数元素就是该元素的个数超过数组长度的一半。

所以我们可以让不同的数字相互抵消,最后剩下的数字就是多数元素。

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)

Geekhyt avatar Sep 14 '21 17:09 Geekhyt

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]
        }
    }
};

Givenchy-Coisini avatar Sep 29 '21 02:09 Givenchy-Coisini