iT邦幫忙

DAY 6
0

連續30天,挑戰演算法系列 第 6

[Day06] 30天挑戰演算法 - 一枝獨秀

題目來源Single Number

問題
給予一個 integer 陣列,每一個數字都會出現過兩次,只有一個數字會出現一次,請將那個數字給找出來。
在解此題目時如果可以使用線性的時間複雜度以及不使用額外的記憶體會更好(optional)。

例子
[ 1 3 5 7 9 9 7 5 1 ] -> 答案就是 3 (只出現過一次)
[ 1 3 5 7 9 1 7 9 ] -> 不可能會有這種題目,因為題目說了,只有一個數字會是孤單的,其他**保證**都會出現兩次。

想法
第一次看到這題目時,如果不要使用到額外記憶體,最簡單的方法就是 先排序 在找出沒有伴的 她(他)...
假設題目是 [1 3 5 7 9 1 3 5 7] -> 經由排序後得到 [1 1 3 3 5 5 7 7 9]
接著兩兩相比就可以發現 9 的前後都沒有 9,就可以得知,答案是 9 了。
這個方式的優點是不會使用到 額外的記憶體 , 缺點是在最糟的情況是時間複雜度可能是 O(nLogn) (假設是使用 QuickSort)

後來就發現有一個更快速的方式,既不會用到額外的記憶體,也絕對是線性時間複雜度 O(N)
那就是使用 XOR

常寫程式的人對於 ANDORNOT 一定不陌生,但對於 XOR 可能相對的稍稍陌生了些,但是也一定知道 XOR 這傢伙的存在。因為這是在學習布林運算時的主角之一。

XOR 的特色就是 兩兩相同時會抵銷, 舉例來說:
A XOR A XOR B 得到的答案就會是 B
A XOR A XOR B XOR B XOR D XOR C XOR C 得到的答案就是 D
A XOR B XOR A XOR B XOR C 得到的答案就會是 C

他的邏輯就是:

虛擬碼
所以,根據以上的介紹,這題就變得非常簡單了

assign array[0] to result  
for i in array 1st element to array last element  
assign result xor array i into result  
return result  
  • 如果你用 C# 可以利用我的 測試程式 來驗證
  • 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證
  • 還是想不出來嗎?參考我的吧!

Java 先排序,在兩兩相比
public int singleNumber(int[] A) {
Arrays.sort(A);

boolean isFirstHit = true;
int result = -1;
for (int i = 0; i < A.length; i++) {
if (isFirstHit) {
result = A[i];
isFirstHit = false;
} else {
if (result == A[i])
isFirstHit = true;
else
break;
}
}

return result;
}

C# 解答 採用 XOR
public static int SolutionXOR(int[] A)
{
int result = A[0];
for (int i = 1; i < A.Length; i++)
{
result = result ^ A[i];
}
return result;
}

Python 解答 採用 XOR
def singleNumber(self, A):
if len(A) == 1:
return A[0]

result = A[0]
for i in range(1, len(A), 1):
result = result ^ A[i]
return result


上一篇
[Day05] 二元樹的的中序走訪
下一篇
[Day07] 30天挑戰演算法 - 配對之合
系列文
連續30天,挑戰演算法30
0
mis2000lab
iT邦好手 1 級 ‧ 2014-10-06 10:23:35

哇!好厲害,
您真的把書本上的死知識,寫成範例而且講的很清楚

佩服~

0
海綿寶寶
iT邦超人 1 級 ‧ 2014-10-06 11:36:05

以前學 XOR 只有背那張表就收工了
看到如此的應用
今天算是賺到了
謝謝

0
holmes2136
iT邦新手 3 級 ‧ 2014-10-06 12:33:25

滿有趣的 ~ 多謝分享嚕

我要留言

立即登入留言