deleting duplicates on sorted array
22:28 19 Feb 2012

Just in case you missed, the question is about deleting duplicates on a sorted array. Which can be applied very fast algorithms (compared to unsorted arrays) to remove duplicates.

  • You can skip this if you already know how deleting duplicates on SORTED arrays work

Example:

var out=[];
for(var i=0,len=arr.length-1;i

See?, it is very fast. I will try to explain what just happened.

The sorted arrays *could look like this:

arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];

*the sorting could be ASC or DESC, or by other weird methods, but the important thing is that every duplicated item is next each other.

We stopped at array.length-1 because we don't have anything to check with

Then we added the last element regardless of anything because:

case A:

... ,9,9,9];//we have dup(s) on the left of the last element

case B:

... ,7,9,10];//we don't have dup(s) on the left of the last element

If you really understand what is happening, you will know that we haven't added any 9 on the case A. So because of that, we want to add the last element no matter if we are on case A or B.

Question:

That explained, I want to do the same, but ignoring the undefined value on cases like:

var arr=[];arr[99]=1;//0 through 98 are undefined, but do NOT hold the undefined value

I want to remove those. And on the case I have some real undefined values, these should not be removed.

My poor attempt is this one:

var out=[];
for (var i=0,len=arr.length; i < len - 1;) {
  var x = false;
  var y = false;

  for (var j = i, jo; j < len - 1; j++) {
    if (j in arr) {
      x = true;
      jo = arr[j];
      i = j + 1;
      break;
    }
  }
  if (x == false) {
    break;
  }

  for (var u = i, yo; u < len - 1; u++) {
    if (u in arr) {
      y = true;
      yo = arr[u];
      i = u + 1;
      break;
    }
  }
  if (y == false) {
    out.push(jo);
    break;
  }

  if (jo !== yo) {
    out.push(jo);
  }
}
out.push(arr[len - 1]);

I am really lost, any help is appreciated

javascript arrays duplicates sorting