在長度為 N 的串列中, 其元素 (整數) 應該是 1 到 N, 但有些數字不見了, 其他有些數字則重複出現。該如何找出遺失的數字呢？
題目
在一個長度為 N 的 list 中, 其元素 (整數) 應該是 1 到 N, 但有些數字不見了, 其他有些數字則重複出現。找出遺失的數字, 並放在一個 list 內傳回。
輸入 1: data = [3, 0, 1]
輸出 1: [2]輸入 2: data = [1, 2, 8, 5, 1, 6, 4, 9, 5]
輸出 2: [3, 7]
解題思維
這是刷題網站的經典題目, 難度是 Easy 等級, 大致的做法就是先產生一個 1 到 N 的串列, 再和題目的串列做比較, 就可以找出遺失的數字。所以關鍵就在於串列的排序和比較, 排序有許多演算法可以用, 比較的話通常會使用位元運算。
這裡我們要用 Python 來解, 所以不用搞的這麼複雜, 只要透過 Python 的 Set 來處理就可以了。
解法
我們可以先產生含有完整 1 到 N 數字的 Set, 然後將題目中的串列轉成 Set, 會直接過濾掉重複的數字, 再將兩個 Set 相減, 當你拿一個 Set 減去另一個 Set 時, 你會得到這兩個集合的差集, 就可以找出遺失的數字了。
我們來看一下這段程式, 在呼叫 find_missing_nums() 函式時, 會將題目給的 data 串列 (也就是 [1, 2, 8, 5, 1, 6, 4, 9, 5]) 傳入, 這時會先依據 data 串列的長度, 生成一個 1~9 的 Set, 再指派給 all_data, 函式會將兩個 Set 做差集運算, 然後將運算結果傳回。最後轉成串列後 print 出來, 也就是 [3, 7]。
若這樣還不太明白, 可以用 Python Tutor 的視覺化模式跑一次, 就一清二楚了：
關於 Set 的運算與相關題目, 可參考旗標出版的「Python 刷題鍛鍊班」第 4 章。
