Using recursive function to remove all duplicated array elements

Question

what I want to get is like clean([3,2,3,2,5,1]) == [5,1], for learning purpose, I want to do it using recursive function and vanilla javascript only. The function I wrote is as follows:

r=[];
var clean = function(array){
    var s1=array.slice(0);
    var s2=array.slice(0);
    if(s2[0] !== undefined) {
        r.push(s2.shift());
        for (i=0,flag=false;i<s2.length;i++){
            if (r[r.length-1] == s2[i]){
                s1[i+1]=undefined;
                flag=true;
            }
        }
        if (flag==true){
            r.pop();
            s1.shift();
            for (j=0;j<s1.length;j++){
                if (s1[j] == undefined) {s1.splice(j,1);j--};
            }
        } 
        else{
            s1.shift();
        }
    }
    if (s2.length !== 0) clean(s1);
    return;
}

It seems working, but there are something I don't feel comfortable with:

First of all, I'm very new to programming, when I write javascript functions, I always feel the need to define a variable outside the function to store the result, as r in this case, I know this is a very bad practice and I should define a variable inside the function and just return it. But I spent 6 hours on writing above codes(don't laugh at me), now my brain is totally failing me, I can't think of a way to bring this variable into the function. Any hints are greatly appreciated;

Secondly, when I loop through an array and modify it, its length changes on the go, making the loop unreliable, I had to copy the array to 2 different variables(s1,s2) to avoid looping problem. This is very awkward. Later I think of that I can modify the looping index on the go while the array length changes (as you can see in the j loop), but is this a good practice? The following improved function seems working too:

var ccc = function(array){
    var s1=array.slice(0);
    if(s1[0] !== undefined) {
        r.push(s1.shift());
        for (i=0,flag=false;i<s1.length;i++){
            if (r[r.length-1] == s1[i]){
                s1.splice(i,1);
                i--;
                flag=true;
            }
        }
        if (flag==true){
            r.pop();
        }
        if (s1.length !== 0) ccc(s1);
    }
    return;
}

Besides, I know jQuery probably has a function to achieve this, but if no frame is allowed, what is the best approach(recursive or not)? I briefly search around stackoverflow but find no exact answers.

There was a typo, If you mean the typo by saying the functions is not recursive, I have edited it. I think if a function calls itself, it is recursive, isn't it? — shenkwen
– shenkwen, Commented Oct 25, 2014 at 14:23
Create an empty object. For each value in the array, check to see if it's a property name of the object. If not, add it with the value 0. If it is already a property, set its value to 1. Then iterate through the keys of the object and build a result array from the keys whose value is 0. — Pointy
– Pointy, Commented Oct 25, 2014 at 14:25
"I know jQuery probably has a function to achieve this..." Not likely. jQuery is primarily a DOM manipulation library. — user1106925
– user1106925, Commented Oct 25, 2014 at 14:27
For your second question, you have no j variable. If you meant i and i--, then that's a common way to deal with that problem. — user1106925
– user1106925, Commented Oct 25, 2014 at 14:33

Benjamin Gruenbaum · Accepted Answer · 2014-10-25 14:49:12Z

2

This can be greatly simplified in my opinion. Your code has flags, and a lot of cruft.

Instead, JavaScript arrays already ship with transformation methods - one such method for removing elements from an array you don't want and returning a new array with only the elements you do is .filter.

var clean = myArr.filter(function(el, i, arr){ 
    // filter the array
    // if we return true from here - the element will stay, otherwise it won't
    return (arr.indexOf(el) === i) && (arr.lastIndexOf(el) === i);
});

Basically, our code is saying "the first and last indices of the element are the same as this one" - meaning there is only one element in the array. This is not the fastest way but it's pretty clean and performance shouldn't matter for small arrays anyway. You can put it in a function, of course:

    function clean(arr) {
      return arr.filter(function(el, i) {
        return (arr.indexOf(el) === i) && (arr.lastIndexOf(el) === i);
      });
    }
    alert(clean([3, 2, 3, 2, 5, 1]));

Which I believe is a lot shorter, cleaner and readable than what you started with. In ES6 (next version of the spec JavaScript is based on) and making this a bit slower - this becomes even cleaner:

let clean = (arr) => arr.filter((el, i) => arr.indexOf(el) === arr.lastIndexOf(el));
alert(clean([3, 2, 3, 2, 5, 1]));

answered Oct 25, 2014 at 14:49

Benjamin Gruenbaum

278k90 gold badges524 silver badges524 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Emissary Over a year ago

Wouldn't arr.indexOf(el) === arr.lastIndexOf(el) be cleaner? Matching i is implicit given that the filter function was called in the first place.

Benjamin Gruenbaum Over a year ago

@Emissary yes, but short circuiting would make it also much slower since it would require more iteration in the case arr.indexOf(el) === i

Emissary Over a year ago

oh thanks - I seemed to glance over the last part of your post without spotting you'd already covered that :/

Benjamin Gruenbaum Over a year ago

The 'fast' easy way by the way would be to use a temporary object (or an ES6 Map if available) to make lookup fast instead of using indexOf which iterates the array on every go - this can reduce the runtime from O(n^2) to O(n) but will likely in practice be slower because of cache locality.

Collectives™ on Stack Overflow

Using recursive function to remove all duplicated array elements

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related