剑指offer - 数组中出现次数超过一半的数字 - JavaScript

题目描述:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

题目分析

题目假设很重要,数组非空,且一定存在存在多数的元素。

解法 1: 哈希表统计次数

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

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

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

// ac地址:https://leetcode-cn.com/problems/majority-element/
// 原文地址:https://xxoo521.com/2020-02-07-half-number/

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

    nums.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 的值就是数组中出现次数超过一半的数字了。

// ac地址:https://leetcode-cn.com/problems/majority-element/
// 原文地址:https://xxoo521.com/2020-02-07-half-number/

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let times = 0;
    let result = 0;

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

    return result;
};

时间复杂度 O(N)。空间复杂度是 O(1)。比解法 1 更优。

感谢@ℭ𝔞𝔰𝔱𝔢𝔯的提醒,题目已经假设了一定存在多数的元素,不需要二次遍历进行确定。

拓展思考

如果题目没假设数组中一定存在数目大于一半的元素,例如[1, 2, 3]。此时还需要遍历一遍,统计一下 result 的出现次数。

// ac地址:https://leetcode-cn.com/problems/majority-element/
// 原文地址:https://xxoo521.com/2020-02-07-half-number/

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let times = 0;
    let result = 0;

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

    // 第二次遍历,统计result的次数
    times = 0;
    nums.forEach(number => number === result && times++);

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

更多资料

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×