169. 求众数(简单) - https://leetcode-cn.com/problems/majority-element/submissions/

[tailgo]

1. 打表 执行用时 : 92 ms, 在Majority Element的JavaScript提交中击败了98.40% 的用户 内存消耗 : 37.9 MB, 在Majority Element的JavaScript提交中击败了15.31% 的用户

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var max = nums.length / 2;
    var map = {};
    for (var i = 0; i < nums.length; ++i) {
        if (map[nums[i]]) {
            map[nums[i]]++;
        } else {
            map[nums[i]] = 1;
        }
        if (map[nums[i]] > max) {
            return nums[i];
        }
    }
};

2. 在题解里面看到的使用摩尔投票算法 执行用时 : 68 ms, 在Majority Element的JavaScript提交中击败了100.00% 的用户 内存消耗 : 36.7 MB, 在Majority Element的JavaScript提交中击败了97.76% 的用户

摩尔投票算法 wiki

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var count = 1;
    var m = nums[0];
    for (var i = 1; i < nums.length; ++i) {
        if (nums[i] == m) {
            count++;
        } else if (count == 0) {
            m = nums[i];
            count = 1;
        } else {
            count--;
        }
    }
    return m;
};