付費限定文章

389. Find the Difference (找不同)

英文版點我｜中文版點我

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

我們這樣來讀題目：今天班級裡突然闖進一個陌生人，你拿著兩張相片，分別代表正常和「混入陌生人」的狀況，該如何在最快時間內抓出他呢？

威利在哪裡！我們就從有多一個人的照片著手，每看到人就去另一張照片檢查他有沒有出現。這樣確實能找出混進來的人，可是每個人都要重找一次照片，這太花時間了，有沒有比 O(n^2) 更好的做法？

❶ Sorting

老師於是叫大家照座號排成一列，看看會發生什麼：