首頁 web前端 js教程 javascript數組去重的六種方法總結_javascript技巧

javascript數組去重的六種方法總結_javascript技巧

May 16, 2016 pm 03:44 PM
javascript 數組去重

面試前端必須準備的一個問題:怎麼去掉Javascript的Array的重複項。據我所知,百度、騰訊、盛大等都在面試裡出過這個題目。 這個問題看起來簡單,但其實是暗藏殺機。 考的不僅是實現這個功能,更能看出你對電腦程式執行的深入理解。

    我總共想出了三種演算法來實現這個目的:

Array.prototype.unique1 = 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.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++) //从第二项开始遍历
 {
 //如果当前数组的第i项在当前数组中第一次出现的位置不是i,
 //那么表示第i项是重复的,忽略掉。否则存入结果数组
 if (this.indexOf(this[i]) == i) n.push(this[i]);
 }
 return n;
}
登入後複製

    其中第1種和第3種方法都用到了陣列的indexOf方法。此方法的目的是尋找存入參數在陣列中第一次出現的位置。很顯然,js引擎在實現這個方法的時候會遍歷數組直到找到目標。所以此函數會浪費掉很多時間。 而第2中方法用的是hash表。把已經出現過的透過下標的形式存入一個object內。下標的參考要比用indexOf搜尋數組快的多。

    為了判斷這三種方法的效率如何,我做了一個測試程序,產生一個10000長度的隨機數組成的數組,然後分別用幾個方法來測試執行時間。 結果顯示第二種方法遠快於其他兩種方法。 但是記憶體佔用方面應該第二種方法比較多,因為多了一個hash表。這就是所謂的空間換時間。  就是這個測試頁面,你也可以去看看。

根據hpl大牛的思路,我寫了第四種方法:

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;
}
登入後複製

    這個方法的想法是先將陣列排序,然後比較鄰近的兩個數值。 排序的時候用的JS原生的sort方法,JS引擎內部應該是用的快速排序吧。 最終測試的結果是此方法運行時間平均是第二種方法的三倍左右,不過比第一種和第三種方法快了不少。

第五種方法

最近在做【搜尋歷史記錄】功能也用到,開始用了 indexOf 方法,該方法在 ECMA5才有支持,對於 IE8- 就不支持了。

我們可以自己寫一個函數(Array物件的方法都是定義在原型物件上的),如下:

Array.prototype.unique = function(){
  var length = this.length;
  if(length <= 1){
    return this;
  }
  if(!Array.prototype.indexOf){    
    Array.prototype.indexOf = function(item){
      var l = this.length, i = 0, r = -1;
      if(l <= 0){
         return -1;
       }
      for(; i < l; i++){
        if(this[i] === item){
          r = i;
        }
      }
      return r;
    }
  }
  
  var result = []; //去重数组
  for(var i = 0; i < length; i++){
    if(result.indexOf(this[i]) === -1){
      result.push(this[i]);
    }
  }
  return result;
}
登入後複製

第六種方法

Array型別並沒有提供去重複的方法,如果要把陣列的重複元素幹掉,那得自己想辦法:

function unique(arr) {
  var result = [], isRepeated;
  for (var i = 0, len = arr.length; i < len; i++) {
    isRepeated = false;
    for (var j = 0, len = result.length; j < len; j++) {
      if (arr[i] == result[j]) {  
        isRepeated = true;
        break;
      }
    }
    if (!isRepeated) {
      result.push(arr[i]);
    }
  }
  return result;
}

登入後複製

整體思路是把數組元素逐一搬運到另一個數組,搬運的過程中檢查這個元素是否有重複,如果有就直接丟掉。從嵌套循環就可以看出,這種方法效率極低。我們可以 用一個hashtable的結構來記錄已有的元素,這樣就可以避免內層循環。

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
4 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

如何使用WebSocket和JavaScript實現線上語音辨識系統 如何使用WebSocket和JavaScript實現線上語音辨識系統 Dec 17, 2023 pm 02:54 PM

如何使用WebSocket和JavaScript實現線上語音辨識系統引言:隨著科技的不斷發展,語音辨識技術已成為了人工智慧領域的重要組成部分。而基於WebSocket和JavaScript實現的線上語音辨識系統,具備了低延遲、即時性和跨平台的特點,成為了廣泛應用的解決方案。本文將介紹如何使用WebSocket和JavaScript來實現線上語音辨識系

WebSocket與JavaScript:實現即時監控系統的關鍵技術 WebSocket與JavaScript:實現即時監控系統的關鍵技術 Dec 17, 2023 pm 05:30 PM

WebSocket與JavaScript:實現即時監控系統的關鍵技術引言:隨著互聯網技術的快速發展,即時監控系統在各個領域中得到了廣泛的應用。而實現即時監控的關鍵技術之一就是WebSocket與JavaScript的結合使用。本文將介紹WebSocket與JavaScript在即時監控系統中的應用,並給出程式碼範例,詳細解釋其實作原理。一、WebSocket技

如何利用JavaScript和WebSocket實現即時線上點餐系統 如何利用JavaScript和WebSocket實現即時線上點餐系統 Dec 17, 2023 pm 12:09 PM

如何利用JavaScript和WebSocket實現即時線上點餐系統介紹:隨著網路的普及和技術的進步,越來越多的餐廳開始提供線上點餐服務。為了實現即時線上點餐系統,我們可以利用JavaScript和WebSocket技術。 WebSocket是一種基於TCP協定的全雙工通訊協議,可實現客戶端與伺服器的即時雙向通訊。在即時線上點餐系統中,當使用者選擇菜餚並下訂單

如何使用WebSocket和JavaScript實現線上預約系統 如何使用WebSocket和JavaScript實現線上預約系統 Dec 17, 2023 am 09:39 AM

如何使用WebSocket和JavaScript實現線上預約系統在當今數位化的時代,越來越多的業務和服務都需要提供線上預約功能。而實現一個高效、即時的線上預約系統是至關重要的。本文將介紹如何使用WebSocket和JavaScript來實作一個線上預約系統,並提供具體的程式碼範例。一、什麼是WebSocketWebSocket是一種在單一TCP連線上進行全雙工

PHP 陣列去重時指定移除重複元素的依據 PHP 陣列去重時指定移除重複元素的依據 Apr 28, 2024 pm 10:48 PM

PHP的array_unique()函數用來移除陣列中重複元素,其預設使用嚴格相等(===)。我們可以透過自定比較函數來指定去重依據:建立自定比較函數,指定去重的標準(例如根據元素長度);將自訂比較函數作為第三個參數傳遞給array_unique()函數,即可根據指定的標準移除重複元素。

JavaScript與WebSocket:打造高效率的即時天氣預報系統 JavaScript與WebSocket:打造高效率的即時天氣預報系統 Dec 17, 2023 pm 05:13 PM

JavaScript和WebSocket:打造高效的即時天氣預報系統引言:如今,天氣預報的準確性對於日常生活以及決策制定具有重要意義。隨著技術的發展,我們可以透過即時獲取天氣數據來提供更準確可靠的天氣預報。在本文中,我們將學習如何使用JavaScript和WebSocket技術,來建立一個高效的即時天氣預報系統。本文將透過具體的程式碼範例來展示實現的過程。 We

簡易JavaScript教學:取得HTTP狀態碼的方法 簡易JavaScript教學:取得HTTP狀態碼的方法 Jan 05, 2024 pm 06:08 PM

JavaScript教學:如何取得HTTP狀態碼,需要具體程式碼範例前言:在Web開發中,經常會涉及到與伺服器進行資料互動的場景。在與伺服器進行通訊時,我們經常需要取得傳回的HTTP狀態碼來判斷操作是否成功,並根據不同的狀態碼來進行對應的處理。本篇文章將教你如何使用JavaScript來取得HTTP狀態碼,並提供一些實用的程式碼範例。使用XMLHttpRequest

javascript如何使用insertBefore javascript如何使用insertBefore Nov 24, 2023 am 11:56 AM

用法:在JavaScript中,insertBefore()方法用於在DOM樹中插入一個新的節點。這個方法需要兩個參數:要插入的新節點和參考節點(即新節點將要插入的位置的節點)。

See all articles