169. Majority Element

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个数字数组 nums

要求我们找出其中出现次数找过一半以上的次数（题目保证每个数组都有这个元素）

此外要求我们需要使用 O(n) 时间复杂度与 O(1) 空间复杂度

解题思路

由于题目保证有元素超过了一半以上，所以我们只需要用一个变量 res 记录当前元素、用变量 majorityCount 记录当前元素出现次数

如果当前元素再次出现，我们让 majorityCount++；如果出现其他元素，我们让 majorityCount--

如果 majorityCount === 0，我们更新 res 为当前遍历的元素即可

最后 res 的值为答案

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let res = 0
    let majorityCount = 0

    for(const num of nums) {
        if(majorityCount === 0) {
            res = num
        }

        if(res === num) {
            majorityCount++
        } else {
            majorityCount--
        }
    }

    return res
};