数据结构与算法:异或的妙用(找出一堆数中唯一/唯二出现奇数次的项、swap的优化)

发布时间:2023年12月27日

异或的本质是相同为0,不同为1,实际上也就是无进位加法
那么对于任何数x和y,以下公式永远成立

x^0=x
x^x=0
(x^y)^x=x^(y^x)=(x^x)^y=0^y=y//交换律和结合律

也就是说一堆数里面,出现偶数次的项先自己异或,那么就会得0,然后再和出现奇数次的项进行异或,那么最终结果就是自己本身

找出一堆数中唯一/唯二出现奇数次的项

找出一堆数中唯一出现奇数次的项

如果一堆数中,只有一个数出现了奇数次,其他数都出现了偶数次,如何快速的找出这个数。
我们只需要将这堆数逐一异或,那么最后出来的结果就是这个数。
时间复杂度为O(N),空间复杂度为O(1)

public static void printOddTimesNum1(int[] arr){
	int eor=0;
	for(int cur:arr){
		eor^=cur;
	}
		System.out.println(eor);
}

找出一堆数中唯二出现奇数次的项

如果一堆数中,只有a和b出现了奇数次,其他数都出现了偶数次,如何快速的找出a和b。
(不需要找出a和b分别是多少,但是要找出a和b这一对)

我们只需要将这堆数逐一异或,那么最后出来的结果就是a^b,记作eor
在eor的二进制表示中,一定至少存在一位为1,因为a和b不相同,那么异或出来的二进制至少有一位为1,我们记这位为第x位。
那么要么是a在这第x位上为1,要么是b在这第x位上为1.在这我们就假设是a为1。
且一堆数中出现偶数次的项也分为两大部分,要么在这第x位上为1,要么在这第x位上为0。
无论怎样,这一堆数整体会分为两大部分,在这第x位上为1的分类A(包含a),和在这第x为上为0的分类B
我们取这最右侧一位1和分类A的数逐一异或,得到的就是第x位上为1的a(因为假设a在第x位上为1)然后a再与eor异或,就得到b了。
时间复杂度为O(N),空间复杂度为O(1)

public static void printOddTimesNum2(int[] arr){
	int eor=0;
	for(int i=0;i<arr.length;i++){
		eor^=arr[i];
	}
	int rightOne=eor&(~eor+1);
	int onlyOne=0;
	for(int cur:arr){
		if((cur&rightOne)==1){//也可以改为==0,那么最终得到的就是分类B
			onlyOne^=cur;
			}
		}
		System.out.println(onlyOne+" "+(eor^onlyOne));
	}

具体如何提取该数二进制最右侧的1

int a
int rightone = a & (~a+1)

swap的优化

往常swap的代码为:

int temp=a;
a=b;
b=temp;

但是通过异或操作,我们可以省去这额外的一个常数空间。代码如下:

a=a^b;
b=a^b;
a=a^b;

但是注意,a和b一定要是不同的地址,否则就相当于自己和自己异或,会直接变为0

所以,假设a原本存储着信息x,b原本存储着信息y
a=a^b;即,a变为x异或y,b仍为y
b=a^b;即,b变为(x异或y)异或y,即b变为x,a仍为x异或y
a=a^b;即,a变为(x异或y)异或x,即a变为y,b仍为x

本篇文章还是不懂的话可以去看https://www.bilibili.com/video/BV13g41157hK

文章来源:https://blog.csdn.net/zhiaidaidai/article/details/135151818
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。