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

分析：這是一道很新穎的關(guān)于位運(yùn)算的面試題。

首先我們考慮這個(gè)問題的一個(gè)簡單版本：一個(gè)數(shù)組里除了一個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這個(gè)只出現(xiàn)一次的數(shù)字。

這個(gè)題目的突破口在哪里？題目為什么要強(qiáng)調(diào)有一個(gè)數(shù)字出現(xiàn)一次，其他的出現(xiàn)兩次？我們想到了異或運(yùn)算的性質(zhì)：任何一個(gè)數(shù)字異或它自己都等于0。也就是說，如果我們從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，那么最終的結(jié)果剛好是那個(gè)只出現(xiàn)依次的數(shù)字，因?yàn)槟切┏霈F(xiàn)兩次的數(shù)字全部在異或中抵消掉了。

有了上面簡單問題的解決方案之后，我們回到原始的問題。如果能夠把原數(shù)組分為兩個(gè)子數(shù)組。在每個(gè)子數(shù)組中，包含一個(gè)只出現(xiàn)一次的數(shù)字，而其他數(shù)字都出現(xiàn)兩次。如果能夠這樣拆分原數(shù)組，按照前面的辦法就是分別求出這兩個(gè)只出現(xiàn)一次的數(shù)字了。

我們還是從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，那么最終得到的結(jié)果就是兩個(gè)只出現(xiàn)一次的數(shù)字的異或結(jié)果。因?yàn)槠渌麛?shù)字都出現(xiàn)了兩次，在異或中全部抵消掉了。由于這兩個(gè)數(shù)字肯定不一樣，那么這個(gè)異或結(jié)果肯定不為0，也就是說在這個(gè)結(jié)果數(shù)字的二進(jìn)制表示中至少就有一位為1。我們?cè)诮Y(jié)果數(shù)字中找到第一個(gè)為1的位的位置，記為第N位。現(xiàn)在我們以第N位是不是1為標(biāo)準(zhǔn)把原數(shù)組中的數(shù)字分成兩個(gè)子數(shù)組，第一個(gè)子數(shù)組中每個(gè)數(shù)字的第N位都為1，而第二個(gè)子數(shù)組的每個(gè)數(shù)字的第N位都為0。

現(xiàn)在我們已經(jīng)把原數(shù)組分成了兩個(gè)子數(shù)組，每個(gè)子數(shù)組都包含一個(gè)只出現(xiàn)一次的數(shù)字，而其他數(shù)字都出現(xiàn)了兩次。因此到此為止，所有的問題我們都已經(jīng)解決。

基于上述思路，我們不難寫出如下代碼：

/// // Find two numbers which only appear once in an array // Input: data - an array contains two number appearing exactly once, // while others appearing exactly twice // length - the length of data // Output: num1 - the first number appearing once in data // num2 - the second number appearing once in data /// void FindNumsAppearOnce(int data[], int length, int &num1, int &num2) {if (length < 2)return;// get num1 ^ num2int resultExclusiveOR = 0;for (int i = 0; i < length; ++ i)resultExclusiveOR ^= data[i];// get index of the first bit, which is 1 in resultExclusiveORunsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);num1 = num2 = 0;for (int j = 0; j < length; ++ j){// divide the numbers in data into two groups,// the indexOf1 bit of numbers in the first group is 1,// while in the second group is 0if(IsBit1(data[j], indexOf1))num1 ^= data[j];elsenum2 ^= data[j];} }/// // Find the index of first bit which is 1 in num (assuming not 0) /// unsigned int FindFirstBitIs1(int num) {int indexBit = 0;while (((num & 1) == 0) && (indexBit < 32)){num = num >> 1;++ indexBit;}return indexBit; }/// // Is the indexBit bit of num 1? /// bool IsBit1(int num, unsigned int indexBit) {num = num >> indexBit;return (num & 1); }

?

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動(dòng)，書中的分析講解更加詳細(xì)。歡迎關(guān)注。

本題已被九度Online Judge系統(tǒng)收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測試自己的代碼。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(34)-数组中只出现一次的数字[算法]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。