LeetCode[位运算] - #137 Single Number II
编程技术 / houtizong 发布于 2年前 151
要求：
给定一个整型数组，其中除了一个元素之外，每个元素都出现三次。找出这个元素
注意：算法的时间复杂度应为O(n)，最好不使用额外的内存空间
难度：中等
分析：
与#136类似，都是考察位运算。不过出现两次的可以使用异或运算的特性 n XOR n = 0, n XOR 0 = n，即某一位上出现偶数次1将该位置为0，出现奇数次1将该位置为1，这样扫一遍数组即可得到结果。
类似的，对于本题出现三次的情况，我们需要构造一个与异或类似的运算，使某一位出现三次1时置为0，出现3n+1次1时置为1。取三个整型值ones, twos, threes，均初始化为0，分别用于记录某一位出现1的次数。为简单起见，设输入数组M = {1,1, ... 1}, M中元素个数为m，则对于每一个输入项M[i]，令:
twos = twos | ones & M[i]
ones = ones ^ M[i]
threes = ones & threes
ones = ones & ~threes // 当threes为1时将ones和twos置为0
twos = twos & ~threes
故m=3n时，threes = 1, m=3n+1时，ones = 1。
解决方案：
Java - 248ms
public int singleNumber(int[] A) { if(A.length==0) { return 0; } int ones=0, twos=0, threes=0; for (int i=0;i 请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
技术博客集 - 网站简介：
前后端技术：
后端基于Hyperf2.1框架开发,前端使用Bootstrap可视化布局系统生成
网站主要作用：
1.编程技术分享及讨论交流，内置聊天系统;
2.测试交流框架问题，比如：Hyperf、Laravel、TP、beego;
3.本站数据是基于大数据采集等爬虫技术为基础助力分享知识，如有侵权请发邮件到站长邮箱，站长会尽快处理;
4.站长邮箱：[email protected];
文章归档
文章标签
友情链接
