點擊關(guān)注公眾號，Java干貨及時送達
今天，我們來看看騰訊終面的兩道算法題目，看似簡單，但要現(xiàn)場全部做對，也不容易，直接決定了能否拿到騰訊offer, 一起來看看吧。有n個QQ號碼，除1個孤單的QQ號碼外，其余的QQ號碼都是成雙成對的，求這個孤單的QQ號碼，要求：時間復(fù)雜度為O(n), 空間復(fù)雜度為O(1).如果你不懂這個題目的具體意思，那我來畫個動圖，相信你就會明白了。看動圖：兩個520是一對的，兩個216也是一對的，而剩下的111是孤單的。那么，怎么求出111這個孤單的QQ號碼呢？且聽我慢慢道來。
方法1: 直接記錄
先來介紹最直接的方法：遍歷每個元素，記錄每個號碼出現(xiàn)的次數(shù)，比如：hash_map[520] = 2hash_map[216] = 2hash_map[111] = 1
于是乎，可以輕易地看到111出現(xiàn)的次數(shù)是1，所以，孤單的QQ號就是111.然而，這種方法無法通過騰訊的面試，因為空間復(fù)雜度太大，不符合要求。方法2: 排序求解
于是，想到了計算機中最常用的方法：排序法。顯而易見，排序后結(jié)果為：
顯然，排序后就更清楚了，再遍歷一遍，就容易知道孤單的QQ號是111.
一提到排序算法，很顯然知道，時空復(fù)雜度不達標，無法通過騰訊的面試。方法3: 異或求解
遇到這種題目，需要有一定的敏感度，其實就是需要刷題。直接異或搞起：result?=?520?^?216?^?216?^?520?^?111 =?(520?^?520)?^?(216?^?216)?^?111???????= 0 ^ 0 ^ 111???????= 111
根據(jù)異或算法的交換律和結(jié)合律，很容易破解。方法挺巧妙的，也挺實用。顯然，時空復(fù)雜度符合要求，可以通過騰訊的面試。第一題萬事大吉了哦。關(guān)于異或，我們需要知道，相同兩數(shù)的異或值為0，而0和x的異或值仍為x.接下來，我們用實際的程序驗證一下，有興趣的朋友也可以親自動手試下：#include using?namespace?std;int main(){ unsigned int a[] = {520, 216, 216, 520, 111}; unsigned int n = sizeof(a) / sizeof(a[0]); unsigned int result = 0; for(int i = 0; i < n; i++) { result ^= a[i];??} cout << result << endl; // 結(jié)果 111}
有n個QQ號碼，除2個孤單的QQ號碼外，其余的QQ號碼都是成雙成對的，求這2個孤單的QQ號碼，要求：時間復(fù)雜度為O(n), 空間復(fù)雜度為O(1).?????????如果你不懂這個具體題目，那我來畫個動圖，相信你就會明白?？磩訄D：兩個520是一對的，兩個216也是一對的，剩下的734和111是孤單的。?????????那么，怎么求出734和111這兩個QQ號碼呢？我相信，你肯定已經(jīng)放棄了計數(shù)法和排序法，這就對了。異或算法搞起來！1. 探索異或
result?=?520?^?216?^?734?^ 216?^?520?^?111 =?(520?^?520)?^?(216?^?216)?^?734 ^ 111???????=?0?^?0?^?734 ^ 111???????= 734 ^ 111???????= 689
糟糕了，貌似這次用異或算法不靈了。因為題目變難了，題目中有2個孤單數(shù)，上述的689并不是正解。迷茫之際，必須探索新的思路，才有新的出路。我們先來看看二進制異或值的計算方法，如下表格所示：那么，我們來看看734和111的異或過程，其中，a為734，b為111，直接用二進制異或，如下表格所示：可以看到，a和b的異或二進制值是：0000 0010 1011 0001，也就是十進制的689，所以result = 689.由于734和111不同，故異或值不可能是0，因此，對于它們異或值689的二進制值而言，必然存在一個1.可以看到，689的最后一位是1，因此可知：734和111的二進制的最后一位，必然是一個為0，另一個為1.2. 探索分組
接著，我們可以根據(jù)二進制中最后一位是否為1，把原來的數(shù)據(jù)分為兩類。先來看看原來數(shù)據(jù)的二進制值吧：
很顯然，通過上述規(guī)則的劃分，我們把原來的數(shù)據(jù)分成了兩組，分別是上面表格中的紅色部分和藍色部分。接下來，分別對這兩組求異或，就可以得到兩個最后的值，也就是我們苦苦追求的兩個孤單數(shù)，具體如下。result1?=?520?^?216?^?734?^?216?^?520 = (520 ^ 520) ^ (216 ^ 216) ^ 734????????=?734
3. 步驟總結(jié)
Step1:?計算出原數(shù)組的所有數(shù)字的異或值result, result的值必然不為0，且一定是兩個孤單數(shù)的異或值。
Step2: result的二進制中，必然存在第k位的值為1. 以第k位是否為1來作為判斷標準，對原數(shù)組進行劃分。
Step3:?將原數(shù)組二進制第k位為0的數(shù)，認為是第一個集合，并計算出它們的異或值，形成第一個孤單數(shù)。
Step4:?將原數(shù)組二進制第k位為1的數(shù)，認為是第二個集合，并計算出它們的異或值，形成第二個孤單數(shù)。
該算法非常巧妙，時間復(fù)雜度為O(n), 空間復(fù)雜度為O(1), 完全符合題目的要求，可以通過騰訊的面試。
異或算法很巧妙，在面試中也會經(jīng)常用到，需要引起重視。我們也會一步一個腳印，爭取每篇文章講清講透一件事，也希望大家閱讀后有所收獲，心情愉快。
