找到数组中出现一种/两种奇数
题目:一个数组有一种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这个数?
trick
因为异或运算有个特点,满足交换律和结合律,同时有两个重要的特点:
n^n = 0
n^0 = n
异或运算理论上是:相异为1,相同为0,但其实实际应用时最好把异或运算当作无进位加法来看待,这样比较好记忆。
思路
所以。对于该题,所有数字中,只有一种数出现奇数次,而其他数字都是出现的偶数次,所以我们就可以把所有的数都做异或运算,利用n^n = 0的特点,偶数次的必定被异或为0,奇数次的会保留下来,问题就解决了。
// arr中,只有一种数,出现奇数次
public static void printOddTimesNum1(int[] arr){
int eor = 0;
for(int i=0;i<arr.length; i++){
eor ^= arr[i];
}
Systom.out.println(eor);
}
题目二:一个数组有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这个数?
trick 交换a,b的值
a = a ^ b
b = a ^ b
a = a ^ b
思路
这道题还是用异或来解决,具体怎么做呢?
-
首先把全部的数都做一遍异或运算,因为有两种数是奇数,剩下的全是偶数,偶数做异或结果是0,就不用管,所以最后的异或结果是两个奇数的异或,结果为eor,而这两种奇数又不相等(不要杠,杠就是你赢),所以两个奇数的异或结果必定是不等于0的。
-
第二步,我们无法直接从异或结果中找出两个奇数,但是,我们可以从抑或结果中获得一些区别的信息,我们从最后的异或结果中取最后一个1(任何一个1都可以,但是取最后一个1有技巧,比较顺手,所以取最后一个1),这里假设是第八位,因为异或结果中的1,必定代表了这两个奇数在第八位有区别,(一个数在第八位是0,一个数在第八位是1),然后就可以把所有的数分成两类,一类在第八位是1的,一类在第八位是0的。
-
我们在用异或结果err和第八位是1的做异或(第八位是0的碰都不要碰),而第八位是1的出现偶数次的依然不会受到干扰,异或结果依然还是0,只有a/b会被这一次的异或结果抓到,结果为eor1,这样我们就找到了第一个奇数,然后在让eor和eor1做异或,就得到了第二个奇数。
-
其实这道题目的解法就是来自于上面的trick,不过加入了一些偶数个的干扰数,因为偶数个异或结果为0,丝毫不影响。
// arr中,有两种数,出现奇次数
public static void printOddTimesNum2(int[] arr){
int eor = 0;
for(int i=0;i<arr.length;i++){
eor ^= arr[i];
}
// eor = a^b
// eor != 0
// eor必然有一个位置上是1
int rightOne = eor & (~eor + 1); // 提取出最右的1
int onlyOne = 0; //eor
for(int i=0;i<arr.length;i++){
if((arr[i] & rightOne) == 0){ // 我们这里让和最右侧的1异或结果不等于0,相当于我们和第八位为1的一类数做异或,不碰第八位为0的。
onlyOne ^= arr[i];
}
}
Systom.out.println(onlyOne + " " + (onlyOne^eor));
}