【数组中出现次数超过一半的数字】【剑指offer】【2种解法】

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

解法 1: 统计出现次数

借助哈希表，哈希表的键是数字，值是数字出现的次数。整体流程如下：

  • 遍历数组，统计数字和出现次数
  • 遍历哈希表，返回出现次数超过长度一半的数字

注意，这里要使用 ES6 的 Map，不要使用 json 对象。因为 json 对象的键存在着“隐式类型转换”，所有的键会被转换为字符串，从而导致不易排查的 bug。代码实现如下：

// ac地址：https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
// 原文地址：https://xxoo521.com/2020-02-07-half-number/

/**
 * @param {number[]} numbers
 * @return {number}
 */
function MoreThanHalfNum_Solution(numbers) {
    const map = new Map();
    const length = numbers.length;

    numbers.forEach(num => {
        const times = map.get(num);
        if (times === undefined) {
            map.set(num, 1);
        } else {
            map.set(num, times + 1);
        }
    });

    for (const key of map.keys()) {
        if (map.get(key) > length / 2) {
            return key;
        }
    }

    return 0;
}

遍历两次，时间复杂度是 O(N)。哈希表存储次数，空间复杂度是 O(N)。

解法 2（推荐）

题目说了：只可能有 1 个数字的出现次数超过数组长度的一半。也就是说这个数字的出现总数比其他数字的出现次数和还要多。

定义变量 result 和 times。第一次遍历原数组的时候：

  • times = 0，那么 result 等于当前元素，times 变为 1
  • times != 0 且 result != 当前元素，times 减 1
  • times != 0 且 result = 当前元素，times 加 1

遍历完成后，result 的值就是数组中出现次数超过一半的数字了（如果存在的话）。但还需要遍历一遍，统计一下 result 的出现次数。因为对于 [1, 2, 3]，最后 times 为 1，result 为 3，但不符合要求。

// ac地址：https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
// 原文地址：https://xxoo521.com/2020-02-07-half-number/

/**
 * @param {number[]} numbers
 * @return {number}
 */
function MoreThanHalfNum_Solution(numbers) {
    let times = 0;
    let result = 0;

    numbers.forEach(number => {
        if (times === 0) {
            times = 1;
            result = number;
        } else if (number === result) {
            times += 1;
        } else {
            // number !== result
            times -= 1;
        }
    });

    times = 0;
    numbers.forEach(number => number === result && times++);

    return times > numbers.length / 2 ? result : 0;
}

需要遍历 2 次，时间复杂度 O（N）。空间复杂度是 O（1）。比解法 1 更优。

博客地址：剑指 Offer 题解+代码

收藏 Github ：https://github.com/dongyuanxin/blog