169.多数元素

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let countMap = {}
    nums.forEach(n => {
        if (countMap[n]) {
            countMap[n]++
        } else {
            countMap[n] = 1
        }
    })
    let max = 0
    for (let key in countMap) {
        max = Math.max(max, countMap[key])
    }
    for (let key in countMap) {
        if (countMap[key] === max) {
            return key
        }
    }
};

var majorityElement = function (nums) {
    // 投票法，时间复杂度O(n),空间复杂度O(1)
    // 因为多数元素在数组里出现的次数绝对大于n/2，所以用不同元素消去相同元素，剩下的必然是相同元素
    let candidate = nums[0] // 投票对象
    let count = 1 // 投票数
    // 遍历投票对象
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === candidate) { //投票对象相同，票数+1
            count++
        } else { // 投票对象不同，票数-1
            count--
            if (count < 0) {//该元素不是多数元素，更新投票对象candidate并把票数置1
                candidate = nums[i]
                count = 1
            }
        }
    }
    return candidate
}