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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35