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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param array int整型一维数组
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* FindNumsAppearOnce(int* array, int arrayLen, int* returnSize ) {
    // write code here
    int arr[1000001] = {0};
    int size = 0;
    int* temp = (int*)malloc(sizeof(int) * 2);

    for (int i = 0;  i < arrayLen; i++) {
        arr[array[i]]++;
    }

    for (int i = 0; i < 1000001; i++) {
        if (arr[i] == 1) {
            temp[size++] = i;
        }
    }
    
    *returnSize = size;
    return temp;
}

计数排序，空间复杂度较高，时间复杂度 O(n)，但胜在简单直观；

若要达到题目所要求的的空间复杂度，则只能分组异或运算（因为是找两个出现次数仅为1的数，所以必须分组），不容易想到

异或^操作符：是一个位操作符，针对于二进制位（比特位）的操作。

规则：两个数在同一个二进制位（比特位），相同为0；不同为1。

异或操作符的一些性质：1 任何一个数与自己异或都等于0：a^a=0;

2 任何一个数与0进行异或操作等于它自己：a^0=a;

3 异或运算满足交换律,结合律 :a^b=b^a;(a^b)^c=a^(b^c)