给Array本地对象增加一个原型方法，它的用途是删除数组条目中重复的条目(可能有多个)，返回值是一个包含被删除的重复条目的新数组。
形式化描述：
input
Array(size=N)
output
Array1=Array的无重复保序的子集，
无重复是指，对任意a,b属于Array1，a!=b
保序是指，若a在Array的下标小于b在Array的下标，则a在Array1中的下标也小于b在Array的下标
Array2=Array-Array1，保序
realazy给出了一个新解，思路非常清晰：顺序遍历访问每个元素，如果这个元素的值已经访问过了，则加入Array2，否则加入Array1。判断当前元素的值是否已经访问过所采用的方法是顺序遍历已经访问过的所有元素。
易见该算法复杂度约O(N^2)。
我在他的算法框架下稍微做了一些改进，关键在于遍历过程中如何判断当前元素的值是否已经访问过。在原数组值域为正整数且极差（range=max value-min value）不太大的条件下，可以采用简单的"桶"算法。
准备一个长度为range的boolean数组b，初始化全为false。对于原数组中每个值value，如果b[value]=true，则表明这个值访问过，放入Array2，否则放入Array1同时令b[value]=true。
这显然是O(N)的算法，代价是额外的空间复杂度range，而且要求原数组值域为正整数。
不难推广到值域为整数的情形，事实上只需考察桶号value-min(Array)即可转化为正整数的情形。
为了避免range太大造成的空间的浪费，在"桶"算法基础上改进为散列算法，具体说来是线性同余开散列法。目的是将值域压缩映射到一个可控的小的连续正整数子集中，同时保证不同的原象对应的相同的象的概率要尽可能小，也就是说桶与桶之间要尽量负载均衡。
例如这是一个值域为实数的散列函数：
key=hashFun(value)=Math.floor(value)*37%91
这仍然是O(N)的算法，（显然O(N)是所有uniq算法的复杂度下界），好处是可以控制空间的开销，而且可以适应非整数值域，只需要设计相应的散列函数即可。

下面是桶(bucket)算法的实现：
var resultArr = [],
returnArr = [],
origLen = this.length,
resultLen;
var maxv=this[0],minv=this[0];
for (var i=1; i<origLen; ++i){
if(this[i]>maxv)maxv=this[i];
else if(this[i]<minv)minv=this[i];
}
var blen=maxv-minv+1;
var b=new Array(blen);
for(var i=0;i<blen;++i)b[i]=false;
for (var i=0; i<origLen; ++i){
if (b[this[i]-minv]){
returnArr.push(this[i]);
} else {
resultArr.push(this[i]);
b[this[i]-minv]=true;
}
}
resultLen = resultArr.length;
this.length = resultLen;
for (var i=0; i<resultLen; ++i){
this[i] = resultArr[i];
}
return returnArr;
下面是散列(hash)算法的实现
var shuffler = 37
var beta=0.007;
var origLen=this.length
var bucketSize=Math.ceil(origLen*beta);
var hashSet=new Array(bucketSize);
var hashFun = function(value){
var key = (Math.floor(value)*shuffler)%bucketSize;
return key;
}
//init hashSet
for(var i=0;i<bucketSize;i++)hashSet[i]=new Array();
//
var ret=[],self=[];
var key,value;
var bucket,openLen;
var everConflict;
for(var i=0;i<origLen;i++){
value=this[i];
key=hashFun(value);
bucket = hashSet[key];
openLen=bucket.length;//if(openLen>1)return;
everConflict=false;
for(var j=0;j<openLen;j++){
if(bucket[j]==value){
ret.push(value);
everConflict=true;
break;
}
}
if(!everConflict){
bucket.push(value);
self.push(value);
}
}
selfLen = self.length;
this.length = selfLen;
for (i=0; i<selfLen; ++i){
this[i] = self[i];
}
//compute average bucket size
var lens=[],sum=0;
for(var i=0;i<hashSet.length ;++i){lens.push(hashSet[i].length);sum+=hashSet[i].length};
average=sum/hashSet.length;//watch lens,average
return ret;

用k*10000个0~k*100的随机整数测试计算时间(ms)
k 1 2 3 4 5
realazy 240 693 1399 2301 3807
bucket 55 101 141 219 293
hash 214 411 654 844 1083
测试框架借鉴了http://realazy.org/lab/uniq.html
测试环境Firefox2.0.0.6/Ubuntu7.10/2.66GHzP4/1024MBDDR

评论 (0) All

登陆 还没注册？