是真的菜
题目
- Given an array of integers, every element appears three times except for one. Find that single one.
代码及思想：
class Solution { public: /* 思路： 既然数组中重复数的个数为3，那么只要计算每个bit位的和是否为1就行 比如三个重复数他的某个bit位要么全是1要么全是0，相加的话要么是1+1+1=3，或者是0+0+0=0 然后不重复的那个数该bit位为1的话则总和为4或者1，为0的话其总和为3或者0 总和模3后即不重复的那个数的bit位上的数字 同理推得，如果重复的数的个数为m的话就模m就ok */ int singleNumber1(int A[], int n) { if(n==1) return A[0]; int res = 0; for(int i=0;i<32;i++) { int bits = 0; for(int j=0;j<n;j++) bits += ( (A[j] & (1<<i)) >> i ); res |= ((bits%3) << i); } return res; } /* 思路2： 用ones记录出现一次的bits数 tows记录出现两次的bits数 threes记录出现三次的bits数 */ int singleNumber1(int A[], int n) { if(n==1) return A[0]; int ones = 0; int twos = 0; int threes = 0; for(int i=0;i<n;i++) { twos |= ones & A[i]; //用&，如果bit位出现两次则为1，不然为0 ones ^= A[i]; threes = twos & ones; //如果twos和ones上的bit位为1则表示出现3次了，所以用& ones &= ~threes; //ones中去除出现三次的bit位 twos &= ~threes; //twos中去除出现三次的bit位 } return ones; } };
扩展
- 如果重复的数的次数为2？
- 答：直接遍历异或
- 如果重复的数的次数为m(m>2)？
- 答：方法1模m
- 如果重复的数的次数为2，但是不重复的有2个数？
- 答：先遍历异或一遍得到一个数，找到这个数bit位为1的位置，按照这个bit位是否为1将整组数分成两组（不重复的两个数必定分在不同组）
- 如果重复的数的次数为m(m>2)，但是不重复的有2个数？
- 答：用方法1找bits模m为1的bit位，按照这个bit位是否为1将数组分成两组（模m为1表示两个b不重复的数在这个bit位上是不同的）；然后按照方法1分别求不重复的一个数