歡迎光臨
每天分享高質量文章

分享一道解法巧妙的演算法題

(給演算法愛好者加星標,修煉編程內功

作者:苦逼碼農 / 帥地(本文來自作者投稿)

最近碰到很多通過巧妙著運用位運算來巧妙解決複雜問題的演算法,今天分享的這道題,或許能夠開拓你的一些演算法思維。

題目描述

有一組存放 ID 的資料。並且 ID 取值為 0 – (N-1) 之間,其中只有一個 ID 出現的次數為 1,其他的 ID 出現的次數都等於 2,問如何找到這個次數為 1 的 ID ?

解法一:巧用陣列下標

不知道有多少人還記得我之前分享的巧用陣列下標的技巧:一些常用的演算法技巧總結

我的第一想法便是採用下標法來解決,把 ID 作為陣列 arr 的下標,在遍歷 ID 的過程中,用陣列記下每個 ID 出現的次數,即每次遍歷到 ID = n,則 arr[n]++。

之後我們在遍歷陣列 arr,找到 arr[n] = 1 的ID,該下標 n 便是我們要尋找的目的 ID。

這種方法的時間複雜度為 O(N),空間複雜度為 O(N)。

解法二:巧用哈希表

顯然時間複雜度是無法再降低的了,因為我們必須要遍歷所有的 ID,所以時間複雜度最少都得為 O(N)了,所以我們要想辦法降低空間複雜度。

大家想一個問題,假如我們檢測到某個 ID 已經出現了 2 次了,那麼這個 ID 的資料我們還需要儲存記錄嗎?大部分的 ID 都出現了 2 次,這一大部分的資料真的需要儲存嗎?

答是不用的,因為出現 2 次的 ID 不是我們所要找的。所以我們可以優化解法一,我們可以採用哈希表來記錄 ID 出現的次數:利用哈希表記下每個 ID 出現的次數,每次遇見一個 ID,就把這個 ID 放進 哈希表,如果這個 ID 出現了次數已經為 2 了,我們就把這個 ID 從哈希表中移除,最後哈希表只會剩下一個我們要尋找的 ID。

這個方法最好的情況下空間複雜度可以降低到 O(1),最壞的情況仍然了 O(N)。

解法三:巧用位運算

那究竟有沒辦法讓空間複雜度在最壞的情況下也是 O(1) 呢?

答是有的,按就是採用異或運算。異或運算有個特點:

異或運算特點:相同的兩個數異或之後,結果為 0,任何數與0異或運算,其結果不變並且,異或運算支持結合律

所以,我們可以把所有的 ID 進行異或運算,由於那些出現兩次的 ID 通過異或運算之後,結果都為 0,而出現一次的 ID 與 0 異或之後不變,又因為異或支持結合律,所以,把所有 ID 進行異或之後,最後的結果便是我們要找的 ID。

這個方法的空間複雜度為 O(1),巧妙利用了位運算,而且運算的效率是非常高效的。

問題拓展

假如有 2 個 ID 出現的次數為 1,其他 ID 出現的次數都為 2 呢?有該如何解決呢?是否還是可以用位運算呢?

為了方便這裡我們先假設 異或 的符號為 @,

答是必須的,假如這兩個出現一次的 ID 分別為 A, B,則所有 ID 異或後的結果為 [email protected],這時我們遇到的問題是無法確定 A,B的值。

由於 A 和 B 是不一樣的值,所以 [email protected] 的結果不為 0,也就是說,這個異或值的二進制中某一位為1。顯然,A 和 B 中有且僅有一個數的相同位上也為 1。

這個時候,我們可以把所有 ID 分為兩類,一類在這個位上為 1,另一類為 0,那麼對於這兩類,一類會含有 A,另一類會含有 B。於是,我們可以分別計算這兩類 ID 的異或值,幾可得到 A 和 B 的值。

總結

大家做刷題的時候,不妨多加上一個想法:是否可以用的上位運算這種思路。有收穫?不妨來個好看讓更多人看到這篇文章!

【本文作者】

帥地:一個熱愛編程的在校生,我的世界不只有coding,還有writing。目前維護訂閱號「苦逼的碼農」,專註於寫計算機網絡,資料結構等相關文章

    赞(0)

    分享創造快樂