前言
最近為了換工作，準備下面試，開始回顧複習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;
}
}
