js数组去重

本来不打算写基础算法的，觉得只是效率问题。这几天在看某免费视频教学来缓冲一下纸质书的枯燥，这里我应该说一下视频来源的，因为里面的想法不是我原创，是尚学堂白贺翔，先谢谢给我带来了知识。下面说正事。

1. 视频讲到数组去重的一个方法：借助js对象key唯一的特性，将数组元素值作为一个新对象key值，在数组与对象的转换中借助底层实现了去重，然后依次将key取回数组里。代码如下：

function toObject(arr){
　　var obj = {};
　　for(var i=0,j=arr.length; i<j; i++){
　　　　obj[arr[i]]=true;
　　}
　　return obj;
}
function keys(obj){
　　var arr=[];
　　for(var attr in obj){
　　if(obj.hasOwnProperty(attr))
　　　　arr.push(attr);
　　}
　　return arr;
}
function uniq(newarr){
　　return keys(toObject(newarr));
}

我的运行结果的数组是被排过序的，而视频的运行结果并没有被排序（深深地相信是我的问题，如果谁指出一下当感激不尽，这也是我想写下来的原因）。

介绍说这是雅虎YUI的代码，如此比朴素方法效率更高更简单。我想就算借助语言特性这这种比较去重仍然需要对象的方法去实现，效率高在哪了呢？

2.我就自己回顾了最朴素的去重思想，虽然达到O(n^2)，但写起来不见得麻烦。因为上述代码改变了原数组顺序，下面的代码也舍弃顺序换来一点点效率。不然，我能想到的只有将重复元素后面的元素依次前移了。另一种方法是使用额外内存记录去重结果，这也只是牺牲空间效率换取不移动元素。以上说的都是数组无任何规律和启发式信息的情况。

function uniq(arr){
　　for(var i=0,len=arr.length; i<len-1; i++){
　　　　for(var j=i+1; j<len; j++){
　　　　　　if(arr[i]==arr[j]){
　　　　　　　　//去重
　　　　　　　　arr[j] = arr[len-1];
              arr.length--;
              len--;
           }
       }
   }
   return arr;
}

--------

光想想“做一件事”的效果可能不大，说服自己做下去，因为效果很可能是惊人的。就算没有，也记得感恩。

js数组去重

原文：http://www.cnblogs.com/feitan/p/5118558.html