DIV CSS 佈局教程網

刪除已排序陣列中重複元素的兩種寫法
編輯:JavaScript基礎知識     

實務上常會遇到這樣的需求:給定一個已升序排序的陣列,想刪除其中重複的資料,且只使用一個可變長度的陣列。

問題範例

輸入:[1, 1, 2, 2, 3, 3, 4, 5, 7, 10]
輸出:[1, 2, 3, 4, 5, 7, 10]

實作一:倒序遍歷 + splice

從陣列尾端往前檢查,若發現相鄰兩元素相同,就用 splice 移除當前元素。倒序的好處是刪除元素時不會影響尚未檢查的索引:

var arr = new Array(1,1,2,2,3,3,4,5,7,10);
var len = arr.length;
for (var i = len - 1; i >= 1; i--) {
  if (arr[i-1] == arr[i]) {
    arr.splice(i, 1);
  }
}
alert(arr);

實作二:快慢指標覆寫

使用兩個指標,k 指向「已確定不重複」的最後位置,i 向後掃描。當遇到不同元素時,就把它往前覆寫並推進 k。這種做法不需刪除元素,效率通常更好:

var arr = new Array(1,1,2,2,3,3,4,5,7,10);
var len = arr.length;
var k = 0;
for (var i = 1; i < len; i++) {
  if (arr[k] != arr[i]) {
    arr[k+1] = arr[i];
    k++;
  }
}
alert(arr);

小結

兩種寫法都能完成去重,但實作二透過覆寫避免了頻繁的陣列搬移,效能表現通常更佳。若你使用的語言支援泛型集合或 LINQ 等工具(如 C#、VB.NET),也能用更簡潔的方式達成相同目的。

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