付費限定文章

136. Single Number (只出現一次的數字)

英文版點我｜中文版點我

↑看個小廣告，支持好內容↑

❶ Sorting

題目說相同的數字會成對出現，經過排列後它們必然相鄰，我們依序取兩項起來檢查，只要一發現不相同，就代表找到落單者了。

// [3,5,8,8,3]
排列後 [3,3,5,8,8]，第二組 5≠8，落單數字：5

// [9,4,9,2,4]
排列後 [2,4,4,9,9]，第一組 ​2≠4，落單數字：2

❷ Hash Table

這時面試官會淺淺一笑說：排列總需要 O(nlogn)，找得到線性的解法嗎？