169. 多数元素

发表于 分类于 阅读次数：

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

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

示例 1：

1
2
输入：[3,2,3]
输出：3

示例 2：

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

排序取值

1
2
3
4
5
6
7
8
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  nums.sort((a, b) => a - b);
  return nums[(nums.length / 2) >> 0];
};

Boyer-Moore 投票算法

摩尔投票法的核心就是对拼消耗。

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

1
2
3
4
5
6
7
8
9
10
11
var majorityElement = function (nums) {
  let candidate = 0;
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (count == 0) {
      candidate = nums[i];
    }
    candidate === nums[i] ? count++ : count--;
  }
  return candidate;
};