02-异或算法
2. 异或算法
2.1 异或基础
- 0^N == N N^N == 0;
- 记为无进位相加即可,1+1 = 0;
- 异或运算满足交换律和结合。
2.1.1 不用额外变量交换两个数
解法:aba = b,abb = a。
2.1.2 找出现奇数次的数
1. 题目
一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这种数。
2. 思路
数组里每个元素都异或,两两相消,就只剩下奇数次的那个数
3. 代码
public static void main(String[] args) {
int[] arr = {1,3,4,1,3,4,1,3,4,5,1,3,4};
int ans = 0;
for (int i = 0; i < arr.length; i++) {
ans ^= arr[i];
}
System.out.println(ans);
}
2.2 提取右侧(最低位)的1
1. 题目
怎么把一个int类型的数,提取出最右侧(最低位)的1来
2. 思路
1. 取反加一再和原来相与 a&(~a+1)
取反:这样每一位都不一样,之前的0位置都变成了1,假设此时的值为b。
加一:这样在右面+1就可以让他一直进位直到第一个0(也就是没取反的时候的1的位置),假设此时值为c。
相与:此时c的状态是最低的1往右的值都是0,最低一位的1的位置和a相同,这一位再往右每一个都是不一样的,所以相与之后,直接就可以得到结果。
注意: ~a+1 就等于-a,所以也可以写成a&(-a)
2. 直接暴力
先找位置,然后再把1右移
3. 代码
取反加一:
System.out.println((a&(~a+1)));
System.out.println((a&(-a)));
暴力:
private static int findRightest(int a) {
int rightPos = 0;
// 找最低位的1
for(int i = 0; i < 32; i++){
if((a & 1) == 1){
rightPos = i;
break;
}
a = a>>1;
}
a = 1;
// 右移
for (int i = 0; i < rightPos; i++) {
a = a << 1;
}
System.out.println(a);
return a;
}
2.3 找到两种奇数数
1. 题目
一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两种数
2. 思路
全部异或,只留下eor = a^b
因为a != b,所以二进制的ab至少有一位不一样,即eor != 0,也就是至少存在一位为1。
既然有一位为1,代表a,b在这一位不同(异或:同0异1),那么就可以通过这一位来区分数组。
这一位为0的放一边,为1的放一边,分别异或,这样得到的数就可以区分出来ab了。
只要是eor有一位为1就可以区分,具体是哪个无所谓,所以不妨设是最右侧的一个。
3. 代码
private static int[] getAB(int[] arr) {
// 先异或,得到eor=a^b;
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
// 对于ab,最右侧一位的1提取出来
// System.out.println(eor);
int rightest = eor&(-eor);
// System.out.println(rightest);
// 根据这一位来区分属于谁
// 不妨设a在这位为0,b在这位为1
int[] ans = new int[2];
for (int i = 0; i < arr.length; i++) {
if((arr[i] & rightest) == 0){
ans[0] ^= arr[i];
}else{
ans[1] ^= arr[i];
}
}
return ans;
}
2.4 找到出现k次的数
1. 题目
一个数组中有一种数出现K次,其他数都出现了M次,M > 1, K < M,
要求:找到出现了K次的数,额外空间复杂度O(1),时间复杂度O(N)
2. 思路
利用长度为32的数组,记录下每一位置出现1的次数,模M除K就得到二进制的所求数,再转为十进制。
3. 代码
private static int findKTimes(int[] arr, int m, int k) {
int[] times = new int[32];
// 记录所有数的32位的出现的次数
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < times.length; j++) {
if((arr[i]&(1<<j)) != 0){
times[j] ++;
}
}
}
// Arrays.stream(times).forEach(System.out::println);
// 所有数%m/k 得到的数组合成int
int ans = 0;
for (int i = 0; i < times.length; i++) {
times[i] = times[i]%m/k;
}
// 组合成int
for (int i = 0; i < times.length; i++) {
// cur = 1 1 0 1
// times = 1 0 1 1
ans += (times[i]<<i);
}
return ans;
}