題目描述

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

題目分析

劍指Offer（紀念版）P211

① 自己與自己異或為0

② 0與數A異或為A

③ 異或滿足交換律

代碼實現

void FindNumsAppearOnce(int data[], int length, int* num1, int* num2) {if (data == NULL || length < 2)return;int resultExclusiveOR = 0;for (int i = 0; i < length; ++ i)resultExclusiveOR ^= data[i];unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); *num1 = *num2 = 0;for (int j = 0; j < length; ++ j){if(IsBit1(data[j], indexOf1))*num1 ^= data[j];else*num2 ^= data[j];} }// 找到num從右邊數起第一個是1的位 unsigned int FindFirstBitIs1(int num) {int indexBit = 0;while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))){num = num >> 1;++ indexBit;}return indexBit; }// 判斷數字num的第indexBit位是不是1 bool IsBit1(int num, unsigned int indexBit) {num = num >> indexBit;return (num & 1); }

　　

轉載于:https://www.cnblogs.com/xwz0528/p/4896200.html

總結

以上是生活随笔為你收集整理的面试题40：数组中只出现一次的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

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