关于JS数组去重的问题解决

一、问题描述：

var array=[1,45,3,1,4,67,45]，请编写一个函数redup来去掉其中的重复项，即

redup(array);

console.log(array);//[1,45,3,4,67]

二、遍历的思路

首先，我们很自然想到，最终array数组得到了改变，我们可以使用引用类型的按值传递在内部改变arr的值。

因此，我们可以加入一个形式参数：

function redup(arr){
}

当我们执行redup(array)时，实际上array和redup函数中的形式参数arr都指向内存中保存的同一个数组。

现在如何去掉其中的重复项呢？

首先，最容易想到的是遍历：

从arr[0]开始，依次看后面的数组成员是否则与arr[0]相同，若相同，就删除。

第一轮：arr[1]、arr[2]……依次与arr[0]比较；

第二轮：arr[2]、arr[3]……依次与arr[1]比较；

……

第arr.length-1轮：arr[arr.length-2]与arr[arr.length-1]比较。

因此，我们不难写出如下代码：

function redup(arr){
    for(var i=0,len=arr.length;i

我们测试一下结果是否正确：
var array=[1,45,3,1,4,67,45];
redup(array);
console.log(array);//[1, 45, 3, 4, 67]
我们看到结果符合预期。
三、遍历的问题
如果我们观察得更仔细一些，就会发现：
当我们进行第一轮和array[0]的比较，到array[3]和array[0]时，发现两者相同，便会删除array[3]；
这样我们的数组变成[1,45,3,4,67,45]，即原先的array[4]变成 了现在的array[3]。
下一次比较是array[4]和array[0]的比较，即原先的array[5]和array[0]的比较。
我们看到原先的array[4]和array[0]并没有进行比较。即：
每删除一项，就会导致被删除项的后一项未参与比较。
为什么我们的结果是正确的呢？
在我们上面的例子中，被删除项的后一项都与被删除项不相同，因此并不会影响结果，现在我们来看另外的例子：
var array=[1,45,3,1,1,1,4,67,45,45,45];
redup(array);
console.log(array);//[1, 45, 3, 1, 4, 67, 45]
这里显然不是我们想要的结果。
执行array[0]（值为1）与array[3]比较后，将删除array[3]，原array[3]后面的项整体会向前移一位，下次比较是array[0]与array[4]的比较，实质上是array[0]和原array[5]的比较。当然，这里会删除原array[5]。但是原array[4]实际上并没有和array[0]比较，由于原array[4]和array[0]是相同的，故导致结果不正确。
我们可以得出结论：
每删除一项，就会导致被删除项的后一项未能参与比较，而更后面一项却又能正常比较。
四、遍历的改进
由上，改进的一种思路是强行让被删除项的后一项参与比较，若被删除项的后一项也与被删除项一致，将再次删除它。
这也导致新的问题：后面的所有项都要向前再移一个位置。
事实上，鉴于删除项的不确定性和数组项的索引位置被改变，我们可以改进为从后往前遍历：
function redup(arr){
    for(var i=0,len=arr.length;ii;j--)
                {
                    if(arr[j]===arr[i])
                    {
                        arr.splice(j,1);
                    }
                }
        }
}
var array=[1,45,3,1,1,1,4,67,45,45,45];
redup(array);
console.log(array);//[1, 45, 3, 4, 67]
结果符合预期。
五、边界条件判定
现在，我们还不能认为万事大吉了。一个问题时，对于一些特殊情况，函数是否也能返回正确值？
首先，假使数组为空数组：
len的值为0，循环一开始就不会执行，因此实际上函数什么也没做，最终还是空数组，结果符合预期。
假使数组仅有1项：
len的值为1，同样循环一开始就不会执行，函数什么也没做，最终还是原数组，结果符合预期。
即使数组有2项：
len的值为2，外层循环执行1次，内层循环也执行1次，结果符合预期。如：
var b=[1,1];
redup(b);
console.log(b);//[1]
如果有更多的项，那么将符合预期，因此能够正确处理边界条件。
六、栈和队列方法：比较巧妙
事实上，我们还可以有另一种思路：
从前往后依次将数组项取出，若该项尚未取出过，则放入数组尾部，然后去掉该项。若已取出过，则直接抛弃。当完成全部取出操作，原数组已变成去重后的数组。
好处是不用使用循环嵌套，实现的代码如下：
        function redup(arr){
            var temp=[];
            var len=arr.length;
            for (var i=0; i < len; i++) {               
                if (temp.indexof(arr[0])===-1) {
                    temp.push(arr[0]);
                    arr.push(arr[0]);
                }
                arr.shift();
            }
        }       
        var array=[1,45,3,1,1,1,4,67,45,45,45];
        redup(array);
        console.log(array);//[1, 45, 3, 4, 67]  
同样可以正确处理边界条件。
;i++)>