多数元素

题目

题目来源：力扣（LeetCode）

给定一个大小为 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) {
  let stack = [];
  for (let num of nums) {
    // let len = stack.length;
    // if(stack[m-1] === num || !len){
    // 注释的两行等于下一行的if条件
    // 当前遍历的元素和栈顶元素相等 或 空栈 时入栈，否则出栈
    if (!stack.length || num === stack[stack.length - 1]) {
      stack.push(num);
    } else {
      stack.pop();
    }
  }
  // 最后栈中剩下的必然都是是大于一半的那个元素
  return stack[0];
};

摩尔投票法

摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。

算法可以分为两个阶段：

• 对抗阶段：分属两个候选人的票数进行两两对抗抵消
• 计数阶段：计算对抗结果中最后留下的候选人票数是否有效

摩尔投票法用来寻找数组中出现次数超过一半的元素，注意一定是出现次数超过一半，刚好等于一半是不能用这种算法的。 https://blog.csdn.net/happyeveryday62/article/details/104136295

我们可以把这个过程打个比方，比如现在多军对峙，假设阵营A士兵人数比其他方的人数都多，阵营A士兵能以一杀一，那么只要阵营A士兵不杀自己人（相同数字），去杀不同阵营的人（不同数字），那么最后剩下的那些士兵，就是阵营A的士兵。

/**
 * @param {number[]} nums
 * @return {number}
 */
 // 摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」
 // 算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。
var majorityElement = function(nums) {
  // 初始化候选人
  let major = nums[0];
  // 记录票数
  let count = 1;
  for (let i = 1; i < nums.length; i++) {
    if (count == 0) {
      //前面都抵消完了，再重新指定候选人
      count++;
      major = nums[i];
    } 
    else if (major == nums[i]) {
      //自己人票数加1
      count++;
    } 
    else {
      // 不是自己人就消掉一个
      count--;
    }
  }
  return major;
};