题解 | #数组中只出现一次的两个数字#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] nums) {
        // write code here

        // 核心思想：采用异或运算的方法，先求出这两个数字的异或值，再根据最低为1的位分别求出两个数值
        // 算法时间复杂度O(N)，额外空间复杂度O(1)

        // 1.先异或一轮，得到一个异或值，表示两个只出现了一次的数字的异或结果
        int n = nums.length;
        int xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= nums[i];
        }

        // 2.在此基础上，通过位运算得到一个01组成的二进制数，这个数只有一个1，其余位置均为0，且1的那个位置是异或结果的1的最低位
        xor = xor & (~xor + 1);

        // 此时，xor只有一位是1，意义是：两个只出现一次数字在这个位置上数字不同
        // 3.再遍历一轮nums数组，此时根据与xor的与结果分成两组，每一组分别异或出一个值，即为待求值
        int xor1 = 0;
        int xor2 = 0;
        for (int i = 0; i < n; i++) {
            if ((nums[i] & xor) == 0) {
                xor1 ^= nums[i];
            } else {
                xor2 ^= nums[i];
            }
        }

        // 4.按照题意输出结果
        int[] result = new int[2];
        result[0] = Math.min(xor1, xor2);
        result[1] = Math.max(xor1, xor2);
        return result;
    }
}