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

c语言，两种解法

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
//这里两种写法都空间复杂度不为1，因为C语言不带哈希表
//法1：用数组做哈希表，判断出现一次的数
int* FindNumsAppearOnce1(int* array, int arrayLen, int* returnSize ) {
    // write code here
    int* hash = (int*)calloc(1000001, sizeof(int));
    memset(hash, 0, 1000001*sizeof(int));
    int* ret = (int*)malloc(sizeof(int)*2);
    *returnSize = 0;
    for(int i=0; i<arrayLen; i++)
        hash[array[i]]++;
    
    for(int i=0; i<arrayLen; i++){
        if(hash[array[i]] == 1){
            (*returnSize)++;
            if(*returnSize == 1){
                ret[0] = array[i];
            }else{
                ret[1] = array[i];
            }
        }
    }
    if(ret[0]>ret[1]){
        int temp = ret[1];
        ret[1] = ret[0];
        ret[0] = temp;
    }
    return ret;    
}

//法2：使用异或，两个相同的数异或为0，对于只有一个数出现一次的情况，可以直接异或全部元素得出该数字。
//但是对于有两个数出现一次的情况，可以由全部异或，得出这两个数不同的第一bit，由此对包含此bit的数异或即可得出其原值
int* FindNumsAppearOnce(int* array, int arrayLen, int* returnSize ) {
    int XORAll  = 0;            //存储全部异或的值
    int XORA = 0, XORB = 0;     
    int diffFirstBit = 0;                //两个数不同的第一个bit
    int* ret = (int*)malloc(sizeof(int)*2);
    for(int i=0; i<arrayLen; i++){  //全部数异或
        XORAll ^= array[i];
    }

    while((XORAll & 0x1) == 0){   //找出两个数不同的第一个bit   ,按位与运算记得加括号
        diffFirstBit++;
        XORAll = XORAll >> 1;
    }
    
    diffFirstBit = 0x1 << (diffFirstBit); 
    for(int i=0; i<arrayLen; i++){
        if(array[i] & diffFirstBit){
            XORA ^= array[i];
        }else{
            XORB ^= array[i];
        }
    }
    *returnSize = 2;
    ret[0] = XORA < XORB ? XORA : XORB;
    ret[1] = XORA < XORB ? XORB : XORA;
    return ret;
}