1. 题目描述

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

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

2. 思路分析

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

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

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

3. 代码

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
// 检查指定元素的次数是否大于等于长度一半
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