Find and remove int duplicates in an Array

Question

First, I know there is a lot of duplicate answers already, but I can't find what I want, even searched in Google. This is a question asked in an interview.

So, for my question: I have the next int array:

int[] array = {1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9, 9};

EDIT: You can assume that the array is sorted.

I want to get only the distinct values, without the duplicates, meaning:

array = {1, 2, 3, 4, 5, 6, 7, 8, 9, ......};

EDIT: Assume that you don't need to shrink the array, but return the values in their sorted order, and the rest of the values at the end.

There is a couple of instructions:

Don't use any other or new array, meaning use the same array for returning the result.
Don't use any Collections like Set or ArrayList.
Make it the most useful you can.

Iv'e tried to do this with Set, but now I want something different. Also tried to replace the duplicate values with -1 value, but this is true only when I'm assuming that I'm using positive values only.

If you find identical question, tell me and I will delete this one.

Thanks.

A set is what you need to create from that data - which is what the Set class is for. Don't reinvent the wheel. — Evan Mulawski
– Evan Mulawski, Commented Sep 21, 2012 at 12:36
You can't shrink an array so I don't know how you intend to do that. Can you assume the values are sorted already? — Peter Lawrey
– Peter Lawrey, Commented Sep 21, 2012 at 12:40
@Evan Mulawski This what the interviewer asked. Believe me, I was not trying to reinvent the wheel. — Ofir A.
– Ofir A., Commented Sep 21, 2012 at 12:41
Actually, a sentence like the one in the second line of code means that a new array is used. In many languages, in fact, the modification of the size of such an array implies the usage of a new one. What are, therefore, the specific limitations of alternative structure usage? — cangrejo
– cangrejo, Commented Sep 21, 2012 at 12:42

Denys Séguret · Accepted Answer · 2012-09-21 12:50:49Z

9

If they're in order, that's not terribly difficult.

/**
 * removes duplicates in the provided sorted array
 * @return the number of different elements (they're at the beginning)
 */
public static int shrink(int[] array) {
    int w = 0;
    for (int i=0; i<array.length; i++) {
      if (i==0 || array[i]!=array[i-1]) {
          array[w++]=array[i];
      }
    }
    return w;
}

After that, only the first w elements are interesting.

edited Sep 21, 2012 at 12:50

answered Sep 21, 2012 at 12:38

Denys Séguret

384k90 gold badges813 silver badges780 bronze badges

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

4 Comments

Denys Séguret Over a year ago

I edited in order to try to implement also requirement 3 (be the most useful possible).

loler Over a year ago

@dystroy I think you can avoid i==0 in if statement if you write if(array[i]!=array[i+1])

Denys Séguret Over a year ago

@loler I don't think so. Test it with non duplicates at both ends.

loler Over a year ago

@dystroy ok, i think then you have to avoid overload in case of last element.

Collectives™ on Stack Overflow

Find and remove int duplicates in an Array

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