陣列去重是前端面試中的高頻考題,百度、騰訊、盛大等公司都曾採用過。這個問題看似簡單,實則暗藏玄機,考察的不僅是功能實現,更能反映你對程式執行效率的深入理解。
以下先介紹三種常見的去重演算法:
Array.prototype.unique1 = function() { var n = []; //一個新的臨時數組 for(var i = 0; i < this.length; i++) //遍歷當前數組 { if (n.indexOf(this[i]) == -1) n.push(this[i]); } return n; } Array.prototype.unique2 = function() { var n = {},r=[]; //n為hash表,r為臨時數組 for(var i = 0; i < this.length; i++) //遍歷當前數組 { if (!n[this[i]]) //如果hash表中沒有當前項 { n[this[i]] = true; //存入hash表 r.push(this[i]); //把當前數組的當前項push到臨時數組裡面 } } return r; } Array.prototype.unique3 = function() { var n = [this[0]]; //結果數組 for(var i = 1; i < this.length; i++) //從第二項開始遍歷 { if (this.indexOf(this[i]) == i) n.push(this[i]); } return n; }
第一種與第三種方法都使用了陣列的 indexOf,而 js 引擎在實作時會遍歷陣列直到找到目標為止,因此會浪費不少時間。第二種方法則採用 hash 表,透過下標引用的速度遠快於 indexOf 搜尋,效率明顯更高,代價是多佔用一份記憶體,也就是所謂的空間換時間。
最後再補充作者自創的第四種方法,思路是先排序再比較相鄰兩值:
Array.prototype.unique4 = 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; }
測試結果顯示,第四種方法的執行時間約為第二種方法的三倍,但仍比第一、三種快上不少。