題目

• 一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。
  // 請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。

思路

1. 全部元素異或，結(jié)果一定不為0，且結(jié)果為只出現(xiàn)1次的元素的異或。
2. 以第結(jié)果的第一個非0位(假設(shè)第N位)來看，所有元素在該位置的0,1都出現(xiàn)了奇數(shù)次。
3. 以N為基準，為0的分為一組，為1的分為一組。則這兩個數(shù)分別分到2組。
4. 這兩組分別異或，結(jié)果即為所求。

//函數(shù)功能 ： 找出數(shù)組中兩個只出現(xiàn)一次的數(shù)字
//函數(shù)參數(shù) ： arr為源數(shù)組，len為數(shù)組元素個數(shù)，result用來存放結(jié)果
void function1(int *arr, int len, int *result) {
    int i, all = 0, flag = 1;
    for (int i = 0; i < len; ++i) { //所有數(shù)異或
        all ^= arr[i];
    }
    while (!all & flag) {
        flag <<= 1;
    }
    result[0] = result[1] = 0;
    //利用過濾位區(qū)分
    for (i = 0; i < len; i++) {
        if (flag & arr[i])
            result[0] ^= arr[i];
        else
            result[1] ^= arr[i];
    }
}

源碼github