DIV CSS 佈局教程網

用物件當雜湊表,高效率去除陣列重複元素
編輯:JavaScript綜合知識     

陣列去重是面試與實務都常見的小題目。用雙層迴圈比對雖然直觀,時間複雜度卻是 O(n²)。本文這版利用物件的屬性鍵唯一性,把成本壓到接近 O(n)。

核心思路

把每個元素當成物件的鍵寫進暫存物件,重複的值會自然被覆蓋掉。跑完一輪後,再用 for...in 把鍵倒回陣列。因為屬性名只能是字串,這個做法對數字與字串陣列特別合適。

實作

function unique(data) {
    data = data || [];
    var a = {};
    for (var i = 0; i < data.length; i++) {
        var v = data[i];
        if (typeof(a[v]) == 'undefined') {
            a[v] = 1;
        }
    };

    data.length = 0;          // 清空原陣列,保留同一個參考
    for (var i in a) {
        data[data.length] = i;
    }
    return data;
}

function test() {
    var arr = [9, 1, 3, 8, 7, 7, 6, 6, 5, 7, 8, 8, 7, 4, 3, 1];
    var arr1 = unique(arr);
    alert(arr1.join(","));
}
test();

幾個細節值得注意

第一,data.length = 0 是清空而非重新指派的關鍵,這樣外部持有的參考仍指向同一個陣列。第二,for...in 取出的鍵都是字串,所以原本如果是數字,去重後會變成字串,必要時得用 parseFloat 轉回。第三,這個寫法不保證原本的元素順序。

更簡潔的替代方案

若執行環境允許 ES6,直接用 Array.from(new Set(arr)) 或 [...new Set(arr)] 就能一行搞定,語意也更清楚。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved