JZ40-数组中只出现一次的数字

package algo.JZ.A3.JZ40;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class JZ40 {
    public static void main(String[] args) {
        int[] test = new int[]{2, 4, 3, 6, 3, 2, 5, 5};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
//        new Solution().FindNumsAppearOnce(test, num1, num2);
        int[] ints = new Solution2().FindNumsAppearOnce(test);
        System.out.println(Arrays.toString(ints));
    }
}

class Solution {
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        if (array == null || array.length == 0) {
            return;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i])) {
                map.put(array[i], 1);
            } else {
                map.put(array[i], 2);
            }
        }
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (map.get(array[i]) == 1) {
                if (count == 0) {
                    num1[0] = array[i];
                    count++;
                } else {
                    num2[0] = array[i];
                }
            }
        }
    }
}

class Solution2 {
    public void swap(int[] a, int l, int r) {
        int o = a[l];
        a[l] = a[r];
        a[r] = o;
    }

    public int[] FindNumsAppearOnce(int[] array) {
        // write code here
        int[] a = new int[2];
        int x = array[0];
        //将数组中所有数字做异或处理
        //由于相同数字异或结果为0，0与数字x异或的结果为x
        //所以最终的结果为单独出现的数字的异或结果
        for (int i = 1; i < array.length; i++) {
            x ^= array[i];
        }
        int m = 1;
        //两个单独出现的数字若在m位相异，则在x中第m位为1
        while ((m & x) == 0) {
            m = m << 1;///求最后一个二进制位为 1 的数字的位置。1000 1；1000 10；1000 100；1000 1000。m左移4位
        }

//        int m = x & (-x);**********************这样可以直接计算出来m

        //根据第m位的值将原数组分为两组，单独出现的两个数字分在不同的组
        // (英文这两个数字在第m位异或结果为1，即1个为0，一个为1.a&m(1000，为1)==0,b&m==1)
        for (int i : array) {
            if ((m & i) == 0) {
                a[0] ^= i;
            } else {
                a[1] ^= i;
            }
        }
        if (a[0] > a[1]) {
            swap(a, 0, 1);
        }
        return a;
    }
}