题解 | #只出现一次的牛II#

思路

经典题

异或有如下特性

a ^ a = 0,

a != b 必然 a ^ b != 0

根据该特性，把整个数组进行异或和s，必然为非0，而这个非0，必然是由两个孤立的值提供

然后根据s，其中的某一个幂次不为0，进行分组

然后在进行分组求异或和

为啥要这么做呢？

如果一组只有一个孤立值，那异或和必然为孤立值本身

这边通过分组，巧妙地把两个孤立数，分在两个不同的组中。

最后的结果，比对大小，那个小，放在前面。

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] findSingleCowsII (int[] nums) {
        int xor = 0;
        for (int v: nums) {
            xor ^= v;
        }
       // 返回非0的某个幂次
        int pos = Integer.lowestOneBit(xor);

        int v1 = 0, v2 = 0;
        for (int v: nums) {
            // 进行分组
            if ((pos & v) != 0) v1 ^= v;
            else v2 ^= v;
        }
  
        if (v1 > v2) return new int[] {v2, v1};
        else return new int[] {v1, v2};
    }

}