在其他数都出现k次的数组中找到只出现一次的数
版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_27717921/article/details/77435220
这一类问题可以统称为single-num的问题。主要涉及的知识是位运算。
最初是在牛客网上碰到了k=2和k=3的题目，在左老师的书中看到了一般情况，这里来总结一下。
k=2时
Given an array of integers, every element appears twice except for one. Find that single one.
public class Solution {
public int singleNumber(int[] A) {
int result = A[0];
for(int i=1;i<A.length;i++){
result = result^A[i];
}
return result;
}
}k=3
public class Solution {
public int singleNumber(int[] A) {
int[] a = new int[32];
int res = 0;
for(int i=0;i<32;i++){
for(int j=0;j<A.length;j++){
int c =(A[j]>>i)&1;
a[i] = a[i]+c;
}
res=res|(a[i]%3)<<i;
}
return res;
}
}至于为什么采用异或来求解这个问题，左老师在书中是这样说的。
两个k进制的数a和b,在i位上无进位相加的结果为（a(i)+b(i)）%k，如果是k个相同的k进制的数进行无进位I昂家，相加的结果一定是每一位上都是0的k进制数。
因此，我们先设一个32位k进制数组，其实这个数组的大小就为32，并且每一位上都为0，然后遍历数组A，把数组中的一个整数都先转换为k进制，然后在与我们设置的32位的数组进行无进位相加。在遍历结束后，把32位的k进制转换为十进制，k个相同的k进制的无进位相加的结果就是每一位上都是0的k进制，所以那个只出现一次的数则会被剩下来。而k=2的时候就是二进制的异或，当k=3的时候
Single Number的本质，就是用一个数记录每个bit出现的次数，如果一个bit出现两次就归0，这种运算采用二进制底下的位操作^是很自然的。Single Number II中，如果能定义三进制底下的某种位操作，也可以达到相同的效果，Single Number II中想要记录每个bit出现的次数，一个数搞不定就加两个数，用ones来记录只出现过一次的bits，用twos来记录只出现过两次的bits，ones&twos实际上就记录了出现过三次的bits，这时候我们来模拟进行出现3次就抵消为0的操作，抹去ones和twos中都为1的bits
public int singleNumber(int[] A) {
int ones = 0;//记录只出现过1次的bits
int twos = 0;//记录只出现过2次的bits
int threes;
for(int i = 0; i < A.length; i++){
int t = A[i];
twos |= ones&t;//要在更新ones前面更新twos
ones ^= t;
threes = ones&twos;//ones和twos中都为1即出现了3次
ones &= ~threes;//抹去出现了3次的bits
twos &= ~threes;
}
return ones;
}如果对位运算不太熟悉，可以按照左老师写的，将数组A中的每个数都转换为k进制后，在同32位k进制数组累加后转为十进制。
十进制转为k进制
public int[] getKSysNumFormNum(int value,int k){
int[] res = new int[32];
int index=0;
while(value!=0){
res[index++] = value%k;
value = value/k;
}
return res;
}k进制转为十进制
public int getNumFormKSysNum(int[]eo,int k){
int res = 0;
for(int i= eo.length-1;i!=-1;i--){
res = res*k+eo[i];
}
return res;
}OK
腾讯云开发者
