面试题17.10.主要元素

链接：面试题17.10.主要元素
难度：Easy
标签：数组、计数
简介：数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

题解 1 - typescript

• 编辑时间：2021-07-09
• 执行用时：72ms
• 内存消耗：42.6MB
• 编程语言：typescript
• 解法介绍：利用 map 储存所有值。

function majorityElement(nums: number[]): number {
  const map: Map<number, number> = new Map();
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    const num = nums[i];
    map.set(num, (map.get(num) ?? 0) + 1);
  }
  let num: number | null = null;
  for (const [k, v] of map.entries()) if (v > len / 2) num = k;
  return num ?? -1;
}

题解 2 - typescript

• 编辑时间：2021-07-09
• 执行用时：76ms
• 内存消耗：42.1MB
• 编程语言：typescript
• 解法介绍：Boyer-Moore 投票算法。

function majorityElement(nums: number[]): number {
  let candidate = -1;
  let count = 0;
  nums.forEach(num => {
    if (count === 0) candidate = num;
    if (candidate === num) count++;
    else count--;
  });
  count = 0;
  nums.forEach(num => {
    if (candidate === num) count++;
  });
  return count > nums.length / 2 ? candidate : -1;
}