快速排序與去重是 JavaScript 面試中常見的題目,重點在於理解分治思路與不同去重方法的效率差異。
快速排序會先選出一個中間值,把比它小的元素放到左側,比它大的元素放到右側。接著對左右兩個子陣列重複同樣的步驟,直到陣列長度小於二為止,最後再把左側、中間值與右側合併。
這種做法的重點是遞迴與分區。每一輪都會把問題縮小,因此平均效率不錯,但要注意基準值選擇與極端資料可能帶來的效能問題。
第一種方式是逐一取出元素,再與後續元素比較,如果沒有重複就放入新陣列。這種做法直觀,但需要巢狀迴圈,效率較低。
第二種方式是用物件記錄已出現的值。把陣列元素當成物件屬性,每次新增前先判斷屬性是否存在,只需掃描一次,效率較好。
第三種方式是先排序再去重。排序後相同的值會相鄰,只要比較前一個與後一個元素是否相同,就能過濾重複項目。