Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

169. 多数元素 #68

Open
Geekhyt opened this issue Sep 14, 2021 · 1 comment
Open

169. 多数元素 #68

Geekhyt opened this issue Sep 14, 2021 · 1 comment
Labels

Comments

@Geekhyt
Copy link
Owner

Geekhyt commented Sep 14, 2021

原题链接

摩尔投票算法

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

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

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

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 Geekhyt added the 简单 label Sep 14, 2021
@Givenchy-Coisini
Copy link

Givenchy-Coisini commented Sep 29, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants