iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 16
1
Software Development

從LeetCode學演算法系列 第 16

[Day 16] 從LeetCode學演算法 - 0136. Single Number (Easy)

目標:
這題主要目的在於透過題目來介紹前面提過的Bitwise Operation的應用。

原題:

Question:
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4

分析/解題:
給定一個非空的整數陣列,當中每個元素都出現兩次,
只有一個出現一次而已,題目要求找出那個單獨的數字。

在進一步往BST之前,先來一個簡單但一般不會想到的問題。
這題如果我們以暴力法來解的話,假設不用任何額外的資料結構,
我們可以每拿一個數字就對整個陣列做比較,直到找到沒有重複的數字為止。
但這樣除了時間複雜度會是O(N)以外
(對單一數字,所以每個數字都做完就是O(N^2)),
最後會發現有可能會有拿到先前拿過一次的數字,所以顯然是不太行的。

那輔以資料結構呢?
比較常用的方法是使用HashMap(Python則用dict),為每個數字計數,
計數完以後就掃過整個對應,看誰只有被數到一次,就是我們要的答案了。
這個方法要先走訪過一遍陣列,再走訪一遍HashMap或dict,
時間/空間複雜度均為O(N),但還是稍嫌慢了一些。

那有沒有更厲害的解法呢?有!
要了解這個解法怎麼操作,首先我們需要複習一下Bitwise Operation。
當中的XOR的內容是:將兩個數的每個位元兩兩相對,
一個0一個1的時候,結果會是1,否則結果會是0
這可以讓數字運算得到一些神奇的特性,第一個特性是:

a XOR a = 0

我們拿11=1011(二進位)來試試看:

11        = 1011
11        = 1011
11 XOR 11 = 0000 = 0

因為每一位數都相同,XOR後每一位就都會是0。
第二個特性是:

0 XOR a = a, a XOR 0 = a

因為一邊都是0,所以那個位數是0或1,端看原先a的位元。
再來其他一些重要的特性是:

a XOR b = b XOR a (交換律)

(因每個位元的結果端看該位元總共有奇數或偶數個1,和順序無關)

(a XOR b) XOR c = a XOR (b XOR c) = a XOR (c XOR b) = a XOR c XOR b

(不論哪邊先做,結果都是看有奇數個1->結果是1,偶數個1->結果是0)
(最前面的部分是標準的結合律)

推而廣之,我們可以得到XOR具有交換律和結合律
將它的運算的數字左右調換,或者哪個先做,哪個後做,均不影響結果。

回到問題來,假設我們目標的答案是r,
那麼將陣列中所有的數字XOR起來,會發生什麼事情呢?
我們根據前面的已知,將陣列自己調換一下,應該可以變成:
r XOR a XOR a XOR b XOR b XOR c XOR c ……的形式。
(因為怎麼換都不應該影響結果)

於是,陣列全部XOR的結果會等於r XOR 0 XOR 0 XOR…… = r
(其它的兩兩XOR後會變0)

也就是說,將每個數都進行XOR後,結果會留存下那個唯一單獨的數字。
寫成程式碼如下,宣告變數為0後從index 0開始,
或直接將陣列的第一個數指派給它並從index 1開始,
實測上沒有特別感受到時間差異,讀者依照自己的喜好和習慣嘗試即可。

Java的部分用了語法蜜糖
int e:nums代表自nums陣列按順序每次拿一個數並交給e。

Java:

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int e:nums) single ^= e;
        return single;
    }
}

Python:

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        for i in range(1, len(nums)):
            res ^= nums[i]
        return res

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(由於只要整個陣列掃過一次就結束了且無須額外的陣列空間,
時間複雜度為O(N),空間複雜度則為O(1))

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0098. Validate Binary Search Tree (Medium)


上一篇
[Day 15] 從LeetCode學演算法 - 0101. Symmetric Tree (Easy)
下一篇
[Day 17] 從LeetCode學演算法 - 0098. Validate Binary Search Tree (Medium)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言