数组中出现次数超过一半的数字

1. 题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。

由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。

2. 思路分析

数组中有一个数字出现的次数超过数组长度的一半，说明它出现的次数比其他所有数字出现次数的和还要多。

在遍历的过程中保存两个变量：一个数字 + 一个次数。遍历到每个元素都会更新次数，元素 = 数字，加次数；否则，减次数；如果次数为 0，当前元素赋值给数字。

需要注意的是，最后结果不一定符合条件，比如数组 [1, 2, 3]，结果是 3。所以要再统计一下最后数字的次数，是否有一半那么多。

3. 代码

// 检查指定元素的次数是否大于等于长度一半
function checkMoreThanHalf(nums = [], target) {
  let times = 0;
  nums.forEach(num => num === target && ++times);
  return times * 2 >= nums.length;
}

// 计算出数组元素
function moreThanHalfNum(nums = []) {
  if (!Array.isArray(nums) || !nums.length) {
    return null;
  }

  let times = 1,
    result = nums[0];
  for (let i = 1; i < nums.length; ++i) {
    if (times === 0) {
      times = 1;
      result = nums[i];
    } else if (result === nums[i]) {
      ++times;
    } else {
      --times;
    }
  }

  return checkMoreThanHalf(nums, result) ? result : null;
}

/**
 * 以下是测试代码
 */

console.log(moreThanHalfNum([3, 1, 3, 2, 2])); // output: null
console.log(moreThanHalfNum([1, 2, 3, 2, 2, 2, 5, 4, 2])); // output: 2

大师兄

1. 题目描述

2. 思路分析

3. 代码