2013-09-08 10:50:46

一個整型數組中，除了兩個數字之外，其他數字都出現了2次，找出這兩個只出現一次的數字，要求時間復雜度是O(N)，空間復雜度是O(1)。

小結：

任何數與0異或，結果仍為本身；

兩個相同的數字異或，結果為0；

利用異或的以上兩個特點，進行求解。

代碼（測試暫未發現問題，歡迎交流指正！）：

1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 typedef int DataType; 6 7 //返回一個數字的二進制表示中最低位的1的位置 8 size_t GetNumberOfOnce(DataType number) 9 { 10 assert(number != 0); 11 12 size_t mask = 1; 13 size_t cnt = 0; 14 15 while ( !(number & mask) ) 16 { 17 ++cnt; 18 number = number>>1; 19 } 20 21 return (cnt); 22 } 23 24 //找出一個數組中僅出現一次的數字，通過pNumber1、pNumber2返回 25 void GetNumberOfOnce(DataType *array,size_t len,DataType *pNumber1,DataType *pNumber2) 26 { 27 assert(array != NULL); 28 assert(len >= 2); 29 30 *pNumber1 = 0; 31 *pNumber2 = 0; 32 size_t index = 0; 33 size_t resXOR = array[0]; 34 35 for (index = 1;index < len;++index) 36 { 37 resXOR ^= array[index]; 38 } 39 40 size_t positionOf1 = GetNumberOfOnce(resXOR); 41 size_t mask = 1 << positionOf1; 42 43 for (index = 0;index < len;++index) 44 { 45 if (array[index] & mask) //任何數與0異或，結果仍為本身 46 { 47 *pNumber1 ^= array[index]; 48 } 49 else 50 { 51 *pNumber2 ^= array[index]; 52 } 53 } 54 } 55 56 //測試GetNumberOfOnce函數 57 void TestGetNumberOfOnce() 58 { 59 DataType array[10] = {1,2,3,2, 3,5,6,7, 6,5}; 60 //DataType array[10] = {1, 6}; 61 size_t len = 10; 62 DataType number1 = 0; 63 DataType number2 = 0; 64 65 GetNumberOfOnce(array,len,&number1,&number2); 66 cout<<"the numbers appear once are : "<<number1<<"\t"<<number2<<endl; 67 } 68 69 int main() 70 { 71 TestGetNumberOfOnce(); 72 return 0; 73 }

?

測試結果：

the numbers appear once are : 7 1 請按任意鍵繼續. . .

?

轉載于:https://www.cnblogs.com/youngforever/p/3308147.html

總結

以上是生活随笔為你收集整理的【剑指offer】找出数组中出现一次的两个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。