算法-求众数.md

题目

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

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

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解法一

首先想到的是暴力解法，先遍历保存每个数的次数，然后找出最大的

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

这种接法会多用到map这个空间，不是最优解法。题目中有个条件在这个解法中被忽视了：众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。依据这个条件，我们可以推论得到，加入我们将数组排序，那么中间那个数必然是众数。于是可以想到下面这种解法。

解法二

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort((a,b)=>a-b)
    return nums[Math.floor(nums.length/2)]
};

但是js里，sort并不能保证时间复杂度是O(n)。于是查了一些资料，我找到了这道题的最优解法。

摩尔投票法

我们先声明majority，count两个变量，先让majority等于数组第一项，count为1，然后从第二项开始对数组遍历，当到数组第二项，如果第二项不等于majority，这时count减一，然后count等于0，将majority设为第二项，count再设为1。如果第二项等于majority，count加一。接着遍历，依次执行以上逻辑，那么最终结果就是majority。

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

这样时间复杂度就是O(n)了，也没有用到多余的空间。其核心思路在于：

每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。