JavaScript 數組的 uniq 方法
2024-05-06 14:18:29
供稿：網友
給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;
