在数组中出现1次,其他数字出现n次，问题的求解（思路超清晰）
问题1. 在数组中只有一个数字出现1次，其他数字出现两次
思路：可以使用异或运算，异或运算是，一个数与另一个数异或两次那么得到的结果就是他本身题目中只有一个数字出现一次，其他都出现两次，因此将数组中的数字全部进行异或，则得到的就是最终结果
思路：可以使用异或运算，异或运算是，一个数与另一个数异或两次那么得到的结果就是他本身题目中只有一个数字出现一次，其他都出现两次，因此将数组中的数字全部进行异或，则得到的就是最终结果
下面为算法实现：
public static int getNum1From2to1(int[]a) {
int res=0;
for(int i=0;i<a.length;i++) {
res^=a[i];
}
return res;
那么我们提升难度如下：
问题 2. 在数组中只有两个数字出现一次，而其他数字出现两次，请找出这两个出现一次的数字
* 思路：和上面一题类似。因为只有两个数字出现了一次，其他的都出现了两次，因此将数组中的所有元素进行异或运算
* 得到的结果就是出现一次的那两个数之间的异或。得到这个结果就可以这样来处理：
* 首先将上面得到的结果的二进制形式中任意一位1的位置。为什么要得到这个位置呢？因为他们是异或运算因此凡是二进制位
* 为1的位置，说明这两个数这个位不相等。因此可以将数组中的所有数的二进制的这个位置是否为1来进行分组，若为1则和res1进行异或
* 否则和res2进行异或。最终得到的res1和res2即为我们要找的两个数。
* 通俗来说就是这两个数异或得到的结果中二进制位为1的位置 将这两个数分离。 然后进行异或这两个数之间就不会异或了，因为其他数出现了2次
* 因此不会印象最终结果
下面为算法实现：
public static int[] getNum2From2to1(int[]a) {
int[]res=new int[2];
int tem=0;
for(int i=0;i<a.length;i++) {
tem^=a[i];
}
int index;
for(index=0;index<32;index++) {
if((tem&(1<<index))!=0) {
break;
}
}
for(int i=0;i<a.length;i++) {
if((a[i]&(1<<index))!=0) {
res[0]^=a[i];
} else {
res[1]^=a[i];
}
}
return res;
} 最后再来看一个问题：
问题 3.数组a中只有一个数出现一次，其他数出现了3次，找出这个数
* 思路：可以创建一个大小为32的数组用来表示一个int类型的二进制位。将数组中的每个元素的二进制位对应在该数组下标所对应的位置
* 那么可以这样做，判断该数组的该下标位置所对应的数字的二进制的第几为是否为1，若为1则数组对应下标的位置+1。遍历整个数组将所有元素
* 的二进制位为1的位置都这样在32位数组上进行累加。那么就可以这样进行操作：凡是该32位数组元素上存储的数值对3取余不为0那么就可以将该位置
* 对应的二进制数转换为十进制加到结果上。遍历完32位数组即可得到最终结果。
* 解释一下原因：因为只有一个数字出现一次，其他数字出现3次。那么其他数字对应的二进制位置上的数值要么为3要么为3的倍数。只有出现一次的那个数
* 对应的二进制位上的数值对3取余结果不为0。因此可以使用这种方法将该数筛选出来。
*
* 由该算法衍生出来的各种：从其他数出现了n次，只有一个数出现了1次的这种题目都可以这样解决。
问题 3.数组a中只有一个数出现一次，其他数出现了3次，找出这个数
* 思路：可以创建一个大小为32的数组用来表示一个int类型的二进制位。将数组中的每个元素的二进制位对应在该数组下标所对应的位置
* 那么可以这样做，判断该数组的该下标位置所对应的数字的二进制的第几为是否为1，若为1则数组对应下标的位置+1。遍历整个数组将所有元素
* 的二进制位为1的位置都这样在32位数组上进行累加。那么就可以这样进行操作：凡是该32位数组元素上存储的数值对3取余不为0那么就可以将该位置
* 对应的二进制数转换为十进制加到结果上。遍历完32位数组即可得到最终结果。
* 解释一下原因：因为只有一个数字出现一次，其他数字出现3次。那么其他数字对应的二进制位置上的数值要么为3要么为3的倍数。只有出现一次的那个数
* 对应的二进制位上的数值对3取余结果不为0。因此可以使用这种方法将该数筛选出来。
*
* 由该算法衍生出来的各种：从其他数出现了n次，只有一个数出现了1次的这种题目都可以这样解决。
* 下面为算法实现：
public static int getNum1From3to1(int[]a) {
byte[]bb=new byte[32];
for(int i=0;i<a.length;i++) {
for(int j=0;j<bb.length;j++) {
if((a[i]&(1<<j))!=0) {
bb[j]++;
}
}
}
int res=0;
for(int i=0;i<bb.length;i++) {
if(bb[i]%3!=0) {
res |= 1<<i;
}
}
return res;
}
哔哩哔哩公司氛围 96人发布
