DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> 關於JavaScript >> javascript數組去重小結
javascript數組去重小結
編輯:關於JavaScript     

前言

最近為了換工作,准備下面試,開始回顧復習JavaScript相關的知識,昨天下午想到了數組去重的相關方法,干脆整理出幾篇JavaScript算法文章,以備後用,此系列文章不定篇數,不定時間,想到哪寫到哪,不保證正確性,不保證高效率,只是談談個人理解,如有錯誤,請諸位斧正。

關於去重

數組去重是一個比較常見的算法考察點,實現去重的方式無外乎通過唯一性和非唯一性。簡單來講就是挑出唯一的或者刪除不唯一的。以下所有算法都是我自己瞎命名的,請無視之。

循環匹配去重

顧名思義,就是把數組中的每一個元素都和存放元素的數組對比,遇到不重復的元素,放入新數組中,直至循環結束,由於匹配也有循環,也可以稱為雙循環匹配去重,這也是大家都能想到的最簡單的方式。

實現代碼:

var arr=[1,3,4,56,3,7,9,7];
var result=[];
//匹配
function isMatch(array,n){
  for(var i=0;i<array.length;i++){
    if(array[i]==n){
      return true;
    }
  }
  return false;
};
//驗證所有元素
function unqiue(array){
  for(var i=0;i<array.length;i++){
    if(!isMatch(result,array[i])){
      result.push(array[i]);
    }
  }
  return result;
};

console.log(unqiue(arr));

注意:上面方法有一個bug,當存在數字和數字形式的字符串的時候,沒有區分出數字和數字字符串。因為在匹配函數isMatch()裡用的是雙等“==”,沒有驗證元素類型,實際應該使用全等“===”。
修改後的代碼如下:

var arr=[1,3,4,56,3,'1',7,9,7];
var result=[];
//匹配
function isMatch(array,n){
  for(var i=0;i<array.length;i++){
    if(array[i]===n){
      return true;
    }
  }
  return false;
};
//驗證所有元素
function unqiue(array){
  for(var i=0;i<array.length;i++){
    if(!isMatch(result,array[i])){
      result.push(array[i]);
    }
  }
  return result;
};

console.log(unqiue(arr));

算法優缺點:

優點:

實現簡單,思路直觀

缺點:

效率低下

JSON去重/對象去重/字典去重

JSON去重,簡單來講就是利用Object對象key的唯一性,將數組的元素轉換為JSON或者說對象的key值。JSON的value存儲數組的索引index,然後對JSON對象進行for in循環,存儲到新數組中。

Array、JSON、{}都是Object,所以采用任意一種都可以實現此算法。

實現代碼:

Array方式:

var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
  var cache=[];
  var result=[];
   //將數組元素轉為對象的key
  for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
  };
  
  //存儲key(實際的數組元素)
  for(key in cache){
    result.push(key);
  };
  
  return result;
}
  
console.log(unqiue(arr));

JSON方式:

var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
  var cache={};
  var result=[];
   //將數組元素轉為對象的key
  for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
  };
  
  //存儲key(實際的數組元素)
  for(key in cache){
    result.push(key);
  };
  
  return result;
}
  
console.log(unqiue(arr));

Object方式:

var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
  var cache=new Object();
  var result=[];
   //將數組元素轉為對象的key
  for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
  };
  
  //存儲key(實際的數組元素)
  for(key in cache){
    result.push(key);
  };
  
  return result;
}
  
console.log(unqiue(arr));

算法優缺點:

優點:

簡單

效率非常高

缺點:

1.改變了數組元素的類型()
2.有bug(無非區分數字和數字類型字符串)

隊列遞歸去重

昨天晚上思忖良久想到用隊列的方式,先將數組排序成升序或降序的隊列,這樣相同的元素就處在一個區域內,然後從隊尾向前匹配,如果匹配成功,刪除隊尾,然後前一個元素再向其前面的匹配。整個匹配完成之後,剩下的元素就是去重過後的隊列。

var arr=[6, 4, 6, 9, '6', 13, 56, 9, ,'11',1, 8, '7', 17, 5, 45, 3, 7];

function unqiue(array){
  //排序數組,形成隊列
  array.sort(function(m,n){return m-n;});
  ////排序後,隊尾向前對比,如果相同,刪除隊尾,依次類推
  function loop(Index){
    if(Index>=1){
      if(array[Index]===array[Index-1]){
        arr.splice(Index,1);
      }
      loop(Index-1);
    }
    
  }
  loop(array.length-1);
  return array;
}

console.log(unqiue(arr));

算法優缺點:

優點:

效率較高

缺點:

效率不是最高

INDEXOF去重方式

判斷浏覽器是否支持indexOf ,indexOf 為ecmaScript5新方法 IE8以下(包括IE8, IE8只支持部分ecma5)不支持

if (!Array.prototype.indexOf){ 
// 新增indexOf方法 
Array.prototype.indexOf = function(item){ 
var result = -1, a_item = null; 
if (this.length == 0){ 
return result; 
} 
for(var i = 0, len = this.length; i < len; i++){ 
a_item = this[i]; 
if (a_item === item){ 
result = i; 
break; 
} 
} 
return result; 
} 
} 

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