- 一、异或及相关题目
- 1、不使用额外变量交换数组中两个位置元素数
- 2、一个数组中一个数出现了奇数次，剩下数都出现了偶数次，找到并打印
- 3、给定一个整型的数，提取出二进制下最右边的1
- 4、一个数组中两种数字出现了奇数次，其余都出现了偶数次，找到并打印这个数
- 5、一个数组中有一个数出现k次，其他数出现了M次(K < M 且 M > 1,O(N)时间复杂度)
- 异或：一种二进制运算，对应位相同为0，不同为1
- 0 ^ N = 0
- N ^ N = 0
- 1 ^ N = !N
- (a ^ b) ^ c = a ^ (b ^ c)
- a ^ b = b ^ c
- 可以简单理解，遇0不变，遇1翻转
- 要求两个位置不能相同
- 做法：三次异或，设待交换元素分别为a，b
- a = a ^ b
- b = a ^ b (由第一的a b = a ^ b = a ^ b ^ b = a)
- a = a ^ b (由第一步的a和第二步的b a = a ^ b = a ^ b ^ a = b)
- 不能为同一位置是因为 arr[index] = arr[index] ^ arr[index] = 0，这样最终结果都会为0
package xor;
public class Swap {
public static void swap(int[] arr,int index1,int index2){
if(index1 == index2){
return;
}
arr[index1] = arr[index1] ^ arr[index2];
arr[index2] = arr[index1] ^ arr[index2];
arr[index1] = arr[index1] ^ arr[index2];
}
}
2、一个数组中一个数出现了奇数次，剩下数都出现了偶数次，找到并打印
-
由异或特性可知道，一个数异或上自身为0。既然数组中只有一个数出现了一次，剩下都出现偶数次。那么可以把数组元素依次异或，出现偶数次的元素异或后都为0，最后只剩0与奇数次的元素异或，那么得出的就是奇数次元素。
-
举例：arr = [2,4,5,2,4]
result = 2 ^ 4 ^ 5 ^ 2 ^ 4 = (2 ^ 2) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5 （异或满足交换律和结合律，任意数与0异或不变）
package xor;
public class FindOdd {
public static int findOdd(int[] arr){
int result = arr[0];
for(int index = 1;index < arr.length ;index++ ){
result ^= arr[index];
}
return result;
}
}
3、给定一个整型的数，提取出二进制下最右边的1
-
举例 num = 6 = (110)2 ，最右边的1在倒数第二位，返回（010)2 = 2
-
思路：对该数进行取反加1，在与原数进行与运算
6 =- 110
~6 = 001
~6 + 1 = 010
010 ^ 110 = 010
-
取反后，原数二进制尾部为0的位会全部变为1，加上1之后会一直进位到原数最右边1的位置，因为原数进行了取反，所有取反后原数最后右边1的位置为0，再加上1后就是1，此时只有该位为 1 & 1，其他位由于取反的缘故再进行与运算全为0。
package xor;
public class FimdRightOne {
public static int findRightOne(int num){
return num & (~num + 1);
}
}
4、一个数组中两种数字出现了奇数次，其余都出现了偶数次，找到并打印这个数
- 三次异或
- 首先全体异或一次，得出的结果为两个出现奇数次的元素异或
- 找出第一次结果最右边的1，（本质是找到两个出现奇数次元素从低位开始第一个不同的位置）这个数将所有元素分为两类，该位为1和为0
- 如果该位为1则进行异或，这样可以解出一个数，因为偶数次会消掉，两个不同的奇数该位必定不同，所有会得到其中一个
- 将这个数与全体异或一次接出另一个数
package xor;
public class EvenTimes {
public static int[] evenTimes(int[] arr) {
int eor = 0;
//全体异或一次
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
//解出两个数中最右边首先为1的那个数的对应位置
int rightOne = eor & (~eor + 1);
//根据该位将数组元素化为两类，该位1 和 该位0
int onlyOne = 0;
for (int i = 0; i < arr.length; i++) {
if ((rightOne & arr[i]) != 0) {
onlyOne ^= arr[i];
}
}
eor ^= onlyOne;
return new int[]{eor,onlyOne};
}
}
5、一个数组中有一个数出现k次，其他数出现了M次(K < M 且 M > 1,O(N)时间复杂度)
- 生成一个32位数count数组，把所有数字变为32bit表示，若为1则数组的对应位置加1。把数组所有数都进行同样操作过后。依次遍历32位的数组。
- count数组的没个位置元素只能出现两种情况（n * m）和 （n * m + k），n为数组中该位为1的不同数个数。若该位置的数字能整除m，则说明该位置的数是出现m次的，也就是该位置肯定为 n * m。若该位除不尽，则必为（n * m） + k，也就是出现k次的那个数字该位为1。
- 最后找到所有除不尽m的位置，从二进制恢复该元素
- 可能出现一种特殊情况，如果0出现了k次，则需要检查，因为所有位置都能除尽m
package xor;
public class FindKTimesNumber {
public static int findKTimesNumber(int[] arr, int k, int m) {
//将所有数字拆分为32bits的数字
int[] count = new int[32];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j <= 31; j++) {
count[j] += (arr[i] >> j) & 1;
}
}
//恢复出现k次的数字
int res = 0;
for (int i = 0; i < 32; i++) {
if (count[i] % m != k) {
res |= (1 << i);
}
}
//可能出现一种特殊情况，如果0出现了k次，则需要检查，因为所有位置都能除尽m
if (res == 0) {
//记录0出现的次数
int countZero = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
countZero++;
}
}
if (countZero != k) {
return -1;
}
}
return res;
}
}
