LeetCode 137. Single Number II
2023-03-14 09:46:25 时间
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
题目很简单就是数组中所有的数字都出现三次,只有一个数字出现一次,在O(n)的时间复杂度和O(1)的空间复杂度找出这个唯一出现一次的数。
其实我的第一反应是用一个数组记录每一个二进制位出现1的个数,如果不能被3整除,证明所求的数字在该二进制位为1。
思路没问题,但是…………
![](https://img2018.cnblogs.com/blog/670878/201906/670878-20190613235442386-2038941949.png)
![](https://img2018.cnblogs.com/blog/670878/201906/670878-20190613235458799-1106978916.png)
去!你!妹!哦!
相信大家都做过一道面试题,数组中所有的数字都出现两次,只有一个数字出现一次,在O(n)的时间复杂度和O(1)的空间复杂度找出这个唯一出现一次的数。
答案很简单,利用异或的性质,求所有的数字异或和,就是答案。
二进制有两个状态,0 和 1 ,刚好可以对应该二进制位 1 出现的次数 % 2 ,如果 %2 = 1 就是我们要求的。
那如果是出现三次,我们想知道的是一位出现 1 的次数 %3 = 1 的位置。而 %3 为出现 0 1 2 很明显一个二进制位是不够用的,只要用两个二进制位就好了。假设这两个数是 a 和 b
ab
00 --> 0
01 --> 1
10 --> 2
a 表示 第二位 b 表示第一位
但是,这样肯定不能简单通过异或来计算了。我们假设有一种运算为@
![](https://img2018.cnblogs.com/blog/670878/201906/670878-20190614002204210-666563696.png)
这样呢 我们只需要
for x: nums ab = ab @ x
就可以啦~
至于 @ 这个符号具体该怎么计算啊=。=要通过位运算实现啊(硬凑还是能凑出来的。。。可意会不可言传。。。咳。。。
[a, b] = [a ^ ((a | b) & x), (~a) & (b ^ x)]
完整代码:
var singleNumber = function(nums) { let a = 0, b = 0; for (let x of nums) { [a, b] = [a ^ ((a | b) & x), (~a) & (b ^ x)]; } return b; };
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的