利用異或運算去除數(shù)組中重復的數(shù)

風雪夜歸人_95 2014-09-30

展開全文

在網(wǎng)上看到了2013年的一道小米的筆試題，看到了很多文章都是把代碼貼出來了，而對其中蘊含的原理卻不是很了解，因而對代碼上的理解也很困難。于是就有了本文，希望對和我有同樣困惑的讀者有幫助。

廢話少說，首先先重溫一下異或運算的基本知識。
異或運算：一種基于二進制的位運算，特點：同值取0，異值取1.
性質(zhì)：
交換律： a^b = b^a;
結(jié)合律： (a^b)^c = a^(b^c)
對任意的a: a^a = 0; a^0=a; a^(-1) = ~a.

因此，如果有多個數(shù)異或，其中由重復的數(shù)，不論這些重復的數(shù)是否相鄰，如果這些數(shù)重復了偶數(shù)次，則異或后會全部消去；如果重復出現(xiàn)了奇數(shù)次，則會保留一個。
這就是理論基礎(chǔ)。

下面讓我們先看看題目1。
題目1：1-1000放在含有1001個元素的數(shù)組中，只有唯一的一個元素值重復，其它均只出現(xiàn)一次。每個數(shù)組元素只能訪問一次，設(shè)計一個算法，將它找出來；不用輔助存儲空間，能否設(shè)計一個算法實現(xiàn)？

分析：這個問題，我們只需要將除了重復的數(shù)字異或奇數(shù)次，其他數(shù)字異或偶數(shù)次，就可以最后得到這個元素。假設(shè)重復的數(shù)是n，首先將這1001個元素全部異或一遍，結(jié)果用T來表示，即T = 1^2^3^……n^……n^……1000=1^2^3^……1000（T中已經(jīng)不含n）。然后將T和1到1000這1000個元素都異或一遍，最后的結(jié)果就是我們要找的那個元素。
具體編碼：

void found(int a[]) {
       int xors = 0;
       for(int i=0;i<a.length;i++) {
           xors ^= a[i];
       }
       for (int i=0; i< 1000;i++) {
           xors ^= i;
       }
       System.out.println("xors="+xors);
   }

再來看看題目2。
題目2：一個數(shù)組中只有一個數(shù)字出現(xiàn)了一次，其他的全部出現(xiàn)了兩次，求出這個數(shù)字。

分析：有了上面的基礎(chǔ)，是不是感覺很簡單。其思路就是把這所有的數(shù)都異或一遍，得到的就是我們最后需要的那個數(shù)了。

其實上面的題目取了2個極端情況：題目1是只有一個數(shù)字重復了2次，而題目2 是只有一個數(shù)字出現(xiàn)了1次。而在這之間又可以分化出更多的情況，這也是我們要重點看的一道題目。
題目3：在一個長度為n的整形數(shù)組a里，除了三個數(shù)字只出現(xiàn)一次外，其他的數(shù)字都出現(xiàn)了2次。請寫程序輸出任意一個只出現(xiàn)一次的數(shù)字，程序時間和空間復雜度越小越好。
例如： a = {1,3,7,9,5,9,4,3,6,1,7}，輸出4或5或6

分析：可以發(fā)現(xiàn)這里和前面2個題目相比，最大的不同就是有3個數(shù)只出現(xiàn)了1次。這里就不能單純的使用上面的結(jié)論了。這里需要用到另外一個結(jié)論：三個不同的數(shù)兩兩異或得到的三個結(jié)果中，肯定有2個結(jié)果的低位第一個為1的位置相同。（這三個數(shù)總有一個（或2或3個）數(shù)的低位第一個為1 的位數(shù)從右到左數(shù)是最低的，例如是a，a與其他兩個數(shù)異或的結(jié)果低位第一個為1的位數(shù)就一定和a的位數(shù)相同）
根據(jù)這個結(jié)論，我們就有辦法取出其中這個不同的數(shù)。將這3個異或后的結(jié)果分別取最低位中1的位置。然后再將這3個結(jié)果都異或，得到其中不同的那個，那么現(xiàn)在用所有原始數(shù)據(jù)都相互異或后再分別與每個原始數(shù)據(jù)異或，取最低位為1的位置，如果跟上面相同，那么輸出這個數(shù)；
假設(shè)三個出現(xiàn)一次的數(shù)為a,b,c，即把所有的數(shù)異或一次，得到的是T=a^b^c。

代碼如下：

void find(int a[], int n) {
       int i, xors;
       xors = 0;
       for(i=0;i<n;i++) {
           xors ^= a[i];   //得到上面的T
       }
       int fips = 0;
       for(i=0;i<n;++i) {
           fips ^= lowbit(xors ^ a[i]); //fips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)
       }
       int b = 0;
       for(i=0;i<n;++i) {
           if(lowbit(xors ^ a[i]) == fips)//T與每個元素異或并去最低位，判斷是否與fips值相同
               b^=a[i];
       }
       System.out.println("b="+b);
   }

總結(jié)：題目3的要求是打印3個數(shù)中任意一個數(shù)。但是使用這種方式打印出的結(jié)果就是這三個數(shù)中低位為1位置最小的那個數(shù)的值。比如原題中的數(shù)組a,則一定會打印5.