# 268 - Missing Number
題目
暴力法
最簡單的方法之一就是用一個 set 儲存 nums 裡面所有的數字,然後從 0 檢查到 n,看哪個數字不在 set 裡。之所以用 set 是因為搜尋某個數字在不在裡面的效率比 array 高很多。簡單的實作如下:
雖然時間複雜度是 O(n),但空間複雜度也是 O(n),我們能否用 O(1) 的空間複雜度解決這題呢?
Sum 解法
這個 nums 有一個很重要的特性,就是裡面的數字落在 0 到 n 之間,也就是說,假設沒有 missing number,總和就應該是 1 + 2 + ... + n。所以我們可以先把 1 到 n 的總和算出來,然後減掉所有 nums 裡面的 element,剩下的數字就是 missing number 啦。
這個解法就只用 O(1) 的空間複雜度,比剛剛的解法有效率。可惜,這個解法有個缺點,你能想得出來是什麼缺點嗎?
Bitwise XOR 解法
上一個解法的缺點是,如果 n 很大(例如 n 是 INT_MAX),那 sum 就會 overflow,要特別注意。所以我們可以用另一個 Bitwise XOR 解法,這個解法利用的概念是 x ^ x = 0。所以我們可以先把 1 到 n 的所有數字都 XOR 起來,然後再跟 nums 裡面所有的數字 XOR,剩下沒被消掉的數字就是 missing number。
Last updated