|
在網(wǎng)上看到了2013年的一道小米的筆試題，看到了很多文章都是把代碼貼出來了，而對其中蘊(yùn)含的原理卻不是很了解，因而對代碼上的理解也很困難。于是就有了本文，希望對和我有同樣困惑的讀者有幫助。 廢話少說，首先先重溫一下異或運(yùn)算的基本知識。 異或運(yùn)算：一種基于二進(jìn)制的位運(yùn)算，特點(diǎn)：同值取0，異值取1. 性質(zhì)： 交換律： a^b = b^a; 結(jié)合律： (a^b)^c = a^(b^c) 對任意的a: a^a = 0; a^0=a; a^(-1) = ~a. 因此，如果有多個(gè)數(shù)異或，其中由重復(fù)的數(shù)，不論這些重復(fù)的數(shù)是否相鄰，如果這些數(shù)重復(fù)了偶數(shù)次，則異或后會全部消去；如果重復(fù)出現(xiàn)了奇數(shù)次，則會保留一個(gè)。 這就是理論基礎(chǔ)。 下面讓我們先看看題目1。 題目1：1-1000放在含有1001個(gè)元素的數(shù)組中，只有唯一的一個(gè)元素值重復(fù)，其它均只出現(xiàn)一次。每個(gè)數(shù)組元素只能訪問一次，設(shè)計(jì)一個(gè)算法，將它找出來；不用輔助存儲空間，能否設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)？ 分析：這個(gè)問題，我們只需要將除了重復(fù)的數(shù)字異或奇數(shù)次，其他數(shù)字異或偶數(shù)次，就可以最后得到這個(gè)元素。假設(shè)重復(fù)的數(shù)是n，首先將這1001個(gè)元素全部異或一遍，結(jié)果用T來表示，即T = 1^2^3^……n^……n^……1000=1^2^3^……1000（T中已經(jīng)不含n）。然后將T和1到1000這1000個(gè)元素都異或一遍，最后的結(jié)果就是我們要找的那個(gè)元素。 具體編碼：
再來看看題目2。 題目2：一個(gè)數(shù)組中只有一個(gè)數(shù)字出現(xiàn)了一次，其他的全部出現(xiàn)了兩次，求出這個(gè)數(shù)字。 分析：有了上面的基礎(chǔ)，是不是感覺很簡單。其思路就是把這所有的數(shù)都異或一遍，得到的就是我們最后需要的那個(gè)數(shù)了。 其實(shí)上面的題目取了2個(gè)極端情況：題目1是只有一個(gè)數(shù)字重復(fù)了2次，而題目2 是只有一個(gè)數(shù)字出現(xiàn)了1次。而在這之間又可以分化出更多的情況，這也是我們要重點(diǎn)看的一道題目。 題目3：在一個(gè)長度為n的整形數(shù)組a里，除了三個(gè)數(shù)字只出現(xiàn)一次外，其他的數(shù)字都出現(xiàn)了2次。請寫程序輸出任意一個(gè)只出現(xiàn)一次的數(shù)字，程序時(shí)間和空間復(fù)雜度越小越好。 例如： a = {1,3,7,9,5,9,4,3,6,1,7}，輸出4或5或6 分析：可以發(fā)現(xiàn)這里和前面2個(gè)題目相比，最大的不同就是有3個(gè)數(shù)只出現(xiàn)了1次。這里就不能單純的使用上面的結(jié)論了。這里需要用到另外一個(gè)結(jié)論：三個(gè)不同的數(shù)兩兩異或得到的三個(gè)結(jié)果中，肯定有2個(gè)結(jié)果的低位第一個(gè)為1的位置相同。（這三個(gè)數(shù)總有一個(gè)（或2或3個(gè)）數(shù)的低位第一個(gè)為1 的位數(shù)從右到左數(shù)是最低的，例如是a，a與其他兩個(gè)數(shù)異或的結(jié)果低位第一個(gè)為1的位數(shù)就一定和a的位數(shù)相同） 根據(jù)這個(gè)結(jié)論，我們就有辦法 取出其中這個(gè)不同的數(shù)。將這3個(gè)異或后的結(jié)果分別取最低位中1的位置。然后再將這3個(gè)結(jié)果都異或，得到其中不同的那個(gè)，那么現(xiàn)在用所有原始數(shù)據(jù)都相互異或 后再分別與每個(gè)原始數(shù)據(jù)異或，取最低位為1的位置 ，如果跟上面相同，那么輸出這個(gè)數(shù)； 假設(shè)三個(gè)出現(xiàn)一次的數(shù)為a,b,c，即把所有的數(shù)異或一次，得到的是T=a^b^c。 代碼如下：
總結(jié)：題目3的要求是打印3個(gè)數(shù)中任意一個(gè)數(shù)。但是使用這種方式打印出的結(jié)果就是這三個(gè)數(shù)中低位為1位置最小的那個(gè)數(shù)的值。比如原題中的數(shù)組a,則一定會打印5. |
|
|
