Remove duplicates algorithm, in place and stable (javascript) - Stack Overflow

admin管理员组

文章数量:1328574

In class today we were asked to write an algorithm.

Given an array, remove duplicate values:

• It should be stable, and shouldn't have to use an inner loop.
• Should be done in place, as best as possible
• No use of built in functions (I was only allowed to use .push)

After wrestling with it for a while, this is what I came up with.

function remove_dupes(arr){
  var seen = {};
  var count = 0;

  for( var i = 0; i < arr.length - count ; i++) {
    arr[i] = arr[i+count];

    if( seen[arr[i]] ) {
      count++;
      arr[i] = arr[i+count];
      i--;
    }

    seen[arr[i]] = true;
  }

  arr.length = arr.length - count;
}

Working JSBin

I have a bit of repeated code here and I feel that maybe the i-- isn't the best way to go.

Is there any way I could improve this code (without using built in functions)?

In class today we were asked to write an algorithm.

Given an array, remove duplicate values:

• It should be stable, and shouldn't have to use an inner loop.
• Should be done in place, as best as possible
• No use of built in functions (I was only allowed to use .push)

After wrestling with it for a while, this is what I came up with.

function remove_dupes(arr){
  var seen = {};
  var count = 0;

  for( var i = 0; i < arr.length - count ; i++) {
    arr[i] = arr[i+count];

    if( seen[arr[i]] ) {
      count++;
      arr[i] = arr[i+count];
      i--;
    }

    seen[arr[i]] = true;
  }

  arr.length = arr.length - count;
}

Working JSBin

I have a bit of repeated code here and I feel that maybe the i-- isn't the best way to go.

Is there any way I could improve this code (without using built in functions)?

• javascript
• algorithm
• duplicates

Share Improve this question Follow edited Sep 10, 2015 at 20:18 ahnkee asked Sep 10, 2015 at 19:24 ahnkeeahnkee 1451010 bronze badges 2

• I actually think the code looks pretty good as written. It's hard to write in-place code that looks anywhere near as neat as solutions that work on immutable objects. – ivern Commented Sep 10, 2015 at 19:44
• Thanks for your feedback. I'm pretty early in my course so they're drilling the basics/fundamentals as much as possible into us. My intuition hasn't developed to a point where I can look at something and know if it's an optimal solution on my own, so SO has been a great help – ahnkee Commented Sep 10, 2015 at 20:15

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 7

Finally, I think I got what you want without creating a new array:

function remove_dupes(arr){
  var seen = {};
  
  var k = 0;
  for( var i=0; i<arr.length ;i++) {
    if( !seen[arr[i]] ) {
      arr[k++] = arr[i];
      seen[arr[i]] = 'seen';
    }
  }
  
  arr.length = k;
}


var x = [ 1, 2, 1, 4, 5, 3, 'dojo', 4, 6, 6, 7, 7, 6, 7, 5, 6, 6, 6, 6, 7, 'dojo', 11 ];
remove_dupes(x);


document.write(x);

Hope it helps.

This seems like a simpler solution to me:

function remove_dupes(arr){
  var seen = {};
  var dupes_removed = [];

  for( var i = 0; i < arr.length; i++) {
    if (!seen[arr[i]]) {
      dupes_removed.push(arr[i]);
      seen[arr[i]] = true;
    }
  }

  return dupes_removed;
}

This runs in somewhere between O(n) and O(nlogn) time (because JS hash lookups are between O(1) and O(logn) time). This also guarantees the result will be stable. The other solutions so far either run in O(n^2) or aren't stable.

You can use indexOf to see if that value exists in arr than push to a new one

function remove_dupes(arr){
  var newArr = [];
  for( var i = 0; i < arr.length; i++){ 
    if(newArr.indexOf(arr[i]) === -1){
      newArr.push(arr[i]);
    }
  }
  
  return newArr;
}

var myArr = [2,4,2,4,6,6,6,2,2,1,10,33,3,4,4,4];

console.log(remove_dupes(myArr));

You can use Array.prototype.splice to change the array in place (fiddle - look at the console):

var arr = [1, 54, 5, 3, 1, 5, 20, 1, 54, 54];

var seen = {};

var length = arr.length;

var i = 0;

while (i < length) {
    if (seen[arr[i]] !== undefined) {
        arr.splice(i, 1);
        length--;
    } else {
        seen[arr[i]] = true;
    }

    i++;
}

console.log(arr);

This is O(n^2) as splice is O(n), and we iterate n elements.

This is a pact solution I am using in my JS array subclass:

if ( !Array.unique )
{
    Array.prototype.unique = function()
    {
        var tmp = {}, out = [], _i, _n ;
        for( _i = 0, _n = this.length; _i < _n; ++_i )
        if(!tmp[this[_i]]) { tmp[this[_i]] = true; out.push(this[_i]); }
        return out;
    }
}

本文标签： Remove duplicates algorithmin place and stable (javascript)Stack Overflow