首页 > 代码库 > [LeetCode] Single Number II 位运算
[LeetCode] Single Number II 位运算
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Hide Tags
Bit Manipulation 数组中的数均出现3次，只有1个出现一次，可以参考http://www.cnblogs.com/Azhu/articles/3956568.html 说的。
[解题思路]
k为奇数时，如果k 大于10，就不用转换为2进制了，全部的数的同一位叠加（个位上的数叠加，十位上的叠加，百位上的....），mod k 之后结果放回对应位，便是目标int。
如果k <10，将数组中的数转换成2进制，全部数的同一位叠加，后mod k，得到的结果按位的位置还原成目标int。
1 #include <iostream> 2 using namespace std; 3 4 class Solution { 5 public: 6 int singleNumber(int A[], int n) { 7 int cnt[33]={0}; 8 int ret =0; 9 for(int i=0;i<n;i++){10 int curnum = A[i];11 while(curnum){12 int idx= __builtin_ffs (curnum);13 // cout<<idx<<endl;14 cnt[idx]++;15 curnum &=curnum-1;16 }17 }18 // for(int i=1;i<=32;i++)19 // cout<<cnt[i]<<" ";20 // cout<<endl;21 int a=1;22 for(int i=1;i<=32;i++){23 ret +=a*(cnt[i]%3);24 a=a<<1;25 }26 return ret;27 }28 };29 30 int main()31 {32 int a[]={3,5,3,3};33 Solution sol;34 cout<<sol.singleNumber(a,sizeof(a)/sizeof(int))<<endl;35 return 0;36 }
discuss 中有一种使用内存更少的，
https://oj.leetcode.com/discuss/6632/challenge-me-thx
public int singleNumber(int[] A) { int ones = 0, twos = 0; for(int i = 0; i < A.length; i++){ ones = (ones ^ A[i]) & ~twos; twos = (twos ^ A[i]) & ~ones; } return ones;}
直观上难理解，只是思路是一样的，转换为二进制，然后每个位上面的数统计，然后mod(3)，考虑1位，那么他的变化是
0 -> 1 ->2 -> 0
二进制就是：
00 -> 01 -> 10 -> 00
好了，这样只要两位就可以表示了，代码中的ones twos ，就这这个意思。
[LeetCode] Single Number II 位运算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。