每個測試案例包括兩行： 第一行包含一個整數n，表示數組大小。2<=n <= 10^6。 第二行包含n個整數，表示數組元素，元素均為int。 輸出： 對應每個測試案例，輸出數組中只出現一次的兩個數。輸出的數字從小到大的順序。 樣例輸入： 8 2 4 3 6 3 2 5 5 樣例輸出： 4 6 思想：使用 異或 解決問題，一個數異或自己等於0，異或其他數！=0，如果是一個數那麼好辦，異或之後的結果就是我們要的，但是現在是連個數據，那麼我們要想想怎麼講那個數據分開！首先：我們還是先將所有的數進行異或，得到一個結果不等於0哦，那麼在二進制位上必有為1的位(因為那2個數不一樣)，我們可以任意選擇一位，當然，我們習慣選擇最高或者最低位！這一位為1，那麼就意味著第一個數的此位置上為1 ，第二個數此位置上為0，或者反之，不然不可能異或==1！那麼根據這一位的特性，將數組元素分成兩部分！然後分別對這兩部分進行再次異或得到兩個數~^_^ 代碼AC： [cpp] #include <stdio.h> #include <stdlib.h> int find_first_1_bit( int res ) // 每次移位(>>1)後若不能%2 ！= 0 ，則找到 { int n = 0; // 從第0位開始 while( res ) { if( res % 2 == 1 ) { break; } else { res = res >> 1; n++; } } return n; } int judge_N_bit( int num, int N ) // N 從0開始 { return ( num & ( 1 << N ) ); // 取第N位 } int main() { long int n, i; int *num, res, N, t1, t2; while( scanf("%ld", &n) != EOF ) { num = ( int* )malloc( sizeof( int ) * n ); scanf("%d", &res); num[0] = res; for( i = 1; i < n; i++ ) { scanf("%d", &num[i]); res ^= num[i]; } // // 第一次出現1的位置！ N = find_first_1_bit( res ); t1 = 0; t2 = 0; for( i = 0; i < n; i++ ) { if( judge_N_bit( num[i], N ) ) // 若第N位為1 { t2 ^= num[i]; } else // 為0 { t1 ^= num[i]; } } if( t1 < t2 ) { printf("%d %d\n", t1, t2); } else { printf("%d %d\n", t2, t1); } free( num ); } return 0; }
