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

O(N), O(N)

借助哈希表完成,易操作完成

O(N), O(1)

先将原问题稍稍改动，出现一次的数字只有一个。此时只需要将所有数进行异或操作，得到的即是出现一次的数字，因为，a ^ a = 0, a ^ 0 = a, 且 异或操作有交换律，即 a ^ b ^ a = a ^ a ^ b = b。

异或操作：先转换为二进制，然后相同位数，相异为1，相同为0, 4和6, 即0100,0110（只给出四位举例，实际要看int类型的字节数，java中int4个字节，即32位），异或得到0010，即2

但是原题中，出现一次的数字有两个，所以我们要分开这两个数字成为两个组，但是却要保证出现两次的数字都要出现在同一组中。举例1,4,6,1， 我们要分开4和6，先要找到两者不同之处，但是我们首先不知道这两个数位4,6，但是我们可以知道通过所有数异或操作得到2，其实是4 ^ 6，由异或定义，我们知道2某个位数是1时，代表这两个数4,6，这一位数，不相同。我们要找到这一位数，通过与操作，参考代码中mark部分（经典用法）。其中保证出现两次的数字都要出现在同一组中，不用特意处理，因为，用任一数字进行分割都会满足

最后，重新遍历一遍，用k将其分为两组1,1,4和6，即可以得到最终答案

public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] FindNumsAppearOnce (int[] array) {
    // write code here
    //位的异或操作
    int[] res = new int[2];
    int tmp = 0;
    for(int i : array){
        tmp = tmp ^ i;
    }
    //System.out.println(tmp);
    
    int k = 1;
    //找到只出现一次的这两个数字的不相同的第一位（很关键）,用来分为两部分
    while((k & tmp) == 0){//mark
        k = k << 1;//统一向左移动一位
    }
    //System.out.println(k);
    
    for(int i : array){
        if((k & i) == k){
            res[0] ^= i;
        }else{
            res[1] ^= i;
        }
    }
    
    if(res[0] > res[1]){
        int a  = res[0];
        res[0] = res[1];
        res[1] = a;
    }
    
    return res;
}