數組去重的正確編寫姿勢

引言

數組去重是前端面試的一個必備題目，其具體表現內容為：怎樣去掉Javascript的Array的重復項。問題簡單直接，咱們也廢話不多說，直入主題吧。

一般姿勢

使用數組的 indexOf() 方法可以很簡單的達到目的。

Array.prototype.unique = function() {
    // 創建一個新的臨時數組，用于保存輸出結果
    var n = []; 
    // 遍歷當前數組
    for (var i = 0; i < this.length; i++) {
        // 如果當前數組的第i個元素已經保存進了臨時數組，那么跳過，否則把當前項push到臨時數組里面
        if (n.indexOf(this[i]) == -1) n.push(this[i]);
    }
    return n;
} 

再列出一個變換一點的方式。

Array.prototype.unique = function() {
    // 創建一個新的臨時數組，并且把當前數組的第一元素存入到數組中
    var n = [this[0]]; 
    // 從第二項開始遍歷
    for (var i = 1; i < this.length; i++) 
    {
        // 如果當前數組的第i項在當前數組中第一次出現的位置不是i，那么表示第i項是重復的，忽略掉，否則存入結果數組
        if (this.indexOf(this[i]) == i) n.push(this[i]);
    }
    return n;
} 

JS引擎在實現 indexOf() 的時候會遍歷數組直到找到目標為止，此函數會浪費掉很多時間。所有這兩種方式都不是最優的解決方式。

最快姿勢

把已經出現過的元素通過下標的形式存入一個Object內。下標的引用的實現原理利用的是哈希算法，要比用 indexOf() 搜索數組快的多。

Array.prototype.unique = function() {
    // n為hash表，r為臨時數組
    var n = {}, r = [];
    for (var i = 0; i < this.length; i++) {
        // 如果hash表中沒有當前項
        if (!n[this[i]]) {
            // 存入hash表
            n[this[i]] = true;
            // 把當前數組的當前項push到臨時數組里面
            r.push(this[i]); 
        }
    }
    return r;
} 

但從耗時的角度來講，這是最優的一種解決方式。但是從內存占用角度來說，這并不是最優的，因為多了一個hash表。這就是所謂的空間換時間（世間安得雙全法？）。

中庸姿勢

Array.prototype.unique = function() {
    this.sort();
    var re = [this[0]];
    for (var i = 1; i < this.length; i++) {
        if (this[i] !== re[re.length - 1]) {
            re.push(this[i]);
        }
    }
    return re;
} 

這個方法的思路是先把數組排序，然后比較相鄰的兩個值。排序的時候用的JS原生的 sort() 方法，JS引擎內部應該是用的快速排序吧。這種方式比使用 indexOf() 的 一般姿勢 要快，比使用hash表的 最快姿勢 要慢，但是占用內存要少。所以這算是委曲求全的一種 中庸姿勢 。具體要用什么姿勢，各位看官視情況而定吧。

改編自劉春龍博客中的文章 《JS中數組去重問題》