剑指offer-数组中数字出现的次数II-JavaScript

作者 : 开心源码 本文共1668个字,预计阅读时间需要5分钟 发布时间: 2022-05-13 共257人阅读

题目形容:在一个数组 nums 中除一个数字只出现一次之外,其余数字都出现了三次。请找出那个只出现一次的数字。

这题和《LeetCode 137.只出现一次的数字 II》 一样。

解法 1: 最直观的哈希表

处理思路很简单,直接遍历一边数组,而后统计每个数字的出现次数,存入哈希表中。

而后再遍历哈希表中的记录,返回出现次数为 1 的数字。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/single-number-ii/// 原文地址:https://xxoo521.com/2020-03-25-single-number-ii//** * @param {number[]} nums * @return {number} */var singleNumber = function(nums) {    const map = new Map();    for (let num of nums) {        if (map.has(num)) map.set(num, map.get(num) + 1);        else map.set(num, 1);    }    for (let [num, times] of map.entries()) {        if (times === 1) return num;    }};

但是,这种解法利用了额外的O(N)空间来开拓哈希表。

解法 2: 数学计算

假设对于 a、b、c、d 来说,d 出现了 1 次,其余数字出现 3 次。那么求 d 的值的表达式是:2 * d = 3*(a + b + c + d) - (3a + 3b + 3c + d)

为了计算(a + b + c + d),可以将数组去重后,再求和。去重借助的是集合(Set)。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/single-number-ii/// 原文地址:https://xxoo521.com/2020-03-25-single-number-ii//** * @param {number[]} nums * @return {number} */var singleNumber = function(nums) {    const set = new Set(nums);    let sum1 = 0;    for (let num of set.values()) {        sum1 += num;    }    let sum2 = 0;    for (let num of nums) {        sum2 += num;    }    return Math.floor((3 * sum1 - sum2) / 2);};

这种方法还是额外使用了O(N)的空间。

解法 3: 位运算

最符合题目要求的处理方法就是:位运算。能在不开拓额外空间的情况下,完成要求。

按照位数(最高 32 位)去考虑,这种方法的关键就是找到对于只出现一次的数字,它的哪些二进制位是 1。

整体算法流程如下:

  • 从第 1 位开始
  • 创立掩码(当前位为 1,其余为 0),count 设置为 0
  • 将每个数字和掩码进行&运算,假如结果不为 0,count 加 1
  • 假如 count 整除 3,说明出现一次的数字这一位不是 1;否则,说明出现一次的数字这一位是 1
  • 继续检查第 2 位,一直到 32 位,结束

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/single-number-ii/// 原文地址:https://xxoo521.com/2020-03-25-single-number-ii//** * @param {number[]} nums * @return {number} */var singleNumber = function(nums) {    let res = 0;    for (let bit = 0; bit < 32; ++bit) {        let mask = 1 << bit;        let count = 0;        for (let num of nums) {            if (num & mask) ++count;        }        if (count % 3) {            res = res | mask;        }    }    return res;};

时间复杂度是O(N),空间复杂度是O(1)。

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我升级的动力 ??

  • ??Blog:剑指 Offer 题解 + JS 代码
  • ??Github : dongyuanxin/blog
  • ?? 公众号:心谭博客
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 剑指offer-数组中数字出现的次数II-JavaScript

发表回复