当前位置： 移动技术网 > IT编程>开发语言>JavaScript > 关于JS数组去重的问题解决

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

2019年03月20日  | 移动技术网IT编程  | 我要评论

一、问题描述：

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]  


同样可以正确处理边界条件。



						

                    

                        

                            
                        

                    

                    


                    
                    

                        
    
                            
  • 
                                
                            
    • 
                        

                    


                    
                    

                    

                        
您可能感兴趣的文章:

                        
                    

                    

                        如对本文有疑问，
                        点击进行留言回复！！
                    

                


                

                

                    
相关文章:

                    
                

               
                       
                             

                

                    
                    

                        
                        
                        

                        

                            

                                
                                    
                                
                                 
                                    
                                
                            

                            

                                验证码：
                                
                                    
                                    
                                    
                                
                            

                        

                        
                    

                    
                    

                        
                        
                        
                    

                

            

        

        
        
 
            

                

                    
                    

                    
                


                

                    

                        

                            
最近更新的文章

                            

                                
                            

                        

                    

                


                

                    
                    

                        
                    

                


                

                

                    

                        

                            
大家感兴趣的文章

                            

                                
                            

                        

                    

                

                

                    
                    

                        
                    

                


            

        

    



 


 
 

     
    

        

移动技术网