【《漫画算法》笔记】找数组中出现奇数次的元素

给定数组，只有一个元素出现过奇数次

思路：
考虑到异或运算的性质——两个等值数的异或结果等于0，两个不等值的数异或结果为1，
将给定数组的所有元素异或起来，最终结果就是那个“唯一出现过计数次”的数。

给定数组，只有两个元素出现过奇数次

思路：
在上述的基础上，同样对所有元素做异或运算，那么结果必然不是0。也就是说，异或的结果存在某一位非0，假设第a位。这提醒我们，可以根据这个非零位对给定数组中的元素进行分类——分成两类。第一类，二进制表示第a位上为0的元素；第二类，二进制表示第a位上为1的元素。

import java.util.Arrays;

public class findLostNum {
    public static int[] find2Num(int[] arr){
        int[] res=new int[2];

        int xor=0;
        for (int i = 0; i < arr.length; i++) {
            xor^=arr[i];
        }

        if(xor==0){
            return null;
        }

        int sep=1;
        while ((xor&sep)==0){ // 找到xor的二进制表示 最靠右 的‘1’ 的位置
            sep<<=1;
        }
        
        for (int i = 0; i < arr.length; i++) {
            if((sep&arr[i])==0){
                res[0]^=arr[i];
            }else {
                res[1]^=arr[i];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] array=new int[]{4,1,2,2,5,1,4,3};
        int[] res=find2Num(array);
        System.out.println(Arrays.toString(res));

    }
}