面试题 17.10. 主要元素，摩尔投票

面试题 17.10. 主要元素

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
示例 1：

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

示例 2：

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

示例 3：

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

说明：
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

思路

哈希表

哈希表计数，筛选出大于数组个数一半的元素，没有的话返回-1

摩尔投票

摩尔投票，选一个数作为众数。遍历数组相同时加一，不同时减一，如果当前计数为 0，换一个数作为众数代表，继续判断。本题不一定存在众数，如果 count>0 还要判断当前数在原数组中出现的次数应该大于数组长度的一半。

解答

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  const map = {};
  for (const num of nums) {
    if (map[num]) map[num]++;
    else map[num] = 1;
  }
  const arr = Object.entries(map).filter(
    ([key, value]) => value > Math.floor(nums.length / 2)
  );
  return arr.length > 0 ? arr[0][0] : -1;
};

摩尔投票

let count = 0,
  major = null;
for (const num of nums) {
  if (count === 0) {
    major = num;
    count++;
  } else {
    if (major === num) count++;
    else count--;
  }
}
return count > 0 &&
  nums.filter((e) => e === major).length > Math.floor(nums.length / 2)
  ? major
  : -1;