题目:
假设一个数组中有若干个正整数,范围是1~ 100,其中98个整数出现了偶数次,2个整数出现了奇数次,如何找到这两个数?
(如果数组中只有一个出现了奇数次,就直接可以异或运算,结果就是这个数)
import java.util.Arrays;
/**
* @author: daixyhymn
* @description:
* @date: 2020/11/9 17:58
*/
public class FindLostNum {
public static int[] findLostNum(int[] array){
// 保存2个奇数整数
int[] res = new int[2];
// 第一次进行异或运算
int xorRes = 0;
for (int i = 0; i < array.length; i++) {
xorRes ^= array[i];
}
if (xorRes == 0) return null;
// 确定两个整数的不同位,一次来分组
int separator = 1;
while (0 == (xorRes & separator)) {
separator <<= 1;
}
// 第二次分组进行异或运算
for (int i = 0; i < array.length; i++) {
if (0 == (array[i] & separator)) {
res[0] ^= array[i];
} else {
res[1] ^= array[i];
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {2, 2, 3, 1, 4 ,4, 6, 6};
System.out.println(Arrays.toString(findLostNum(arr)));
}
}