专栏首页YuanXin剑指offer - 数组中出现次数超过一半的数字 - JavaScript

剑指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;
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础篇:TypeScript用法与实战

    这篇笔记,主要记录了自己最近在 typescript 实践中的经验。总结了常见的用法。

    心谭博客
  • 【剑指offer:n个骰子的点数】两种思路:递归+动态规划

    题目描述:把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s。输入 n,打印出 s 的所有可能的值出现的概率。

    心谭博客
  • 剑指offer - 把数字翻译成字符串 - JavaScript

    题目描述:给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个...

    心谭博客
  • jenkins "DNSQuestion"日志无限循环问题解决

    资料 https://wiki.jenkins.io/display/JENKINS/Features+controlled+by+system+propert...

    domain0
  • 基于脚本的modelsim自动化仿真

    FPGA的仿真与调试在FPGA开发过程中起着至关重要的作用,也占用了FPGA开发的大部分时间。所以适当减少或简化FPGA的仿真与调试过程无疑是对FPGA开发的加...

    FPGA开源工作室
  • 超实用,Linux中查看文本的小技巧

    查看文本的中间某些行范围之间的内容,例如说查看文本文件100-120行之间的内容:

    cxuan
  • 游戏分析法(三):核心产品决策

    如果要分析一款游戏的基本设定,一般来说,最基本的元素就是“题材”和“玩法”两个部分。这两个方面对于游戏来说互为表里的一体。任何一种玩法,都需要题材的包装,因为大...

    韩伟
  • 05. OCR学习路径之文本检测(下)EAST算法简介

    本次分享主要是讲EAST这篇文章,按照之前的计划是分享两种文本检测思路,即one-stage和two-stage的。已经分享的有《03.OCR学习路径之文本检测...

    Aalto
  • 【机器学习】机器学习分类算法总结

    目前看到的比较全面的分类算法,总结的还不错. 主要分类方法介绍解决分类问题的方法很多,单一的分类方法主要包括:决策树、贝叶斯、人工神经网络、K-近邻、支持向量...

    陆勤_数据人网
  • 机器学习分类算法总结

    目前看到的比较全面的分类算法,总结的还不错. 主要分类方法介绍解决分类问题的方法很多,单一的分类方法主要包括:决策树、贝叶斯、人工神经网络、K-近邻、支持向量...

    机器学习AI算法工程

扫码关注云+社区

领取腾讯云代金券