179.多数元素

题目

给定一个大小为 n的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

    输入：nums = [3,2,3]
    输出：3

示例 2：

    输入：nums = [2,2,1,1,1,2,2]
    输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

想法

可以用一个mp存放，如果这个值没出现就存进去，如果出现了就+1，如果值超过了数组长度的一半就直接返回

实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map()
    for(let i = 0;i < nums.length;i ++){
        if(map.has(nums[i])){
            let times = map.get(nums[i])
            map.set(nums[i], times+1)
            if((times + 1) > (nums.length / 2)) return nums[i]
        }else{
            map.set(nums[i], 1)
        }
    }
    return nums[0]
};

同样的思想，别人写的优雅多了

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let halft = nums.length / 2;
    let map = new Map;
    for(let num of nums){
        if(map.has(num)){
            let currNum = map.get(num);
            map.set(num, currNum + 1)
        }else{
            map.set(num, 1)
        }
        if(map.get(num) > half) return num;
    }
};

其他

看了题解，除了我上面用的是计数法，还有两种解法

排序法

排好序之后，按照题目的规则 ，它一定出现在中间列，向下取整就可以

nums.sort((a,b)=> a - b)
return nums[Math.floor(nums.length / 2)]

摩尔投票法

这几个是在题解评论区复制过来的，觉得是精髓

思想一

核心思想--抵消原则：
在一个数组中，如果某个元素的出现次数超过了数组长度的一半，那么这个元素与其他所有元素一一配对，最后仍然会剩下至少一个该元素。
通过“投票”和“抵消”的过程，可以逐步消除不同的元素，最终留下的候选人就是可能的主要元素。

思想二

候选人(cand_num)初始化为 nums[0]，票数 count 初始化为 1。
当遇到与 cand_num 相同的数，则票数 count = count + 1，否则票数 count = count - 1。
当票数 count 为 0 时，更换候选人，并将票数 count 重置为 1。
遍历完数组后，cand_num 即为最终答案。

投票法是遇到相同的则 票数 + 1，遇到不同的则 票数 - 1。
且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。
因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
这就相当于每个 “多数元素” 和其他元素 两两相互抵消，抵消到最后肯定还剩余 至少1个 “多数元素”。

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

这个方法是满足题目要求的时间复杂度O(n) ， 空间复杂度O(1)