# Removing dups from array

Kevin Behr
Greenhorn
Posts: 23
Hey everyone,

Given a sorted array (of ints), I need to change the array so that any integer that appears only once will appear at the beginning of the SAME array, and still in a sorted order. Also, the program's running time should be proportional to the array (so I cannot have one loop nested inside another loop).

I have done this. However, there is some flaw in my code such that for the following array:

{0,2,2,3,3,7,9,11,11}

My output is:

{0,2,4,7,9}

So, it's not including the last 11. In my attempts to fix this, I have been recieving some out-of-bounds errors. I think I've just been looking at the code for too long. Can anyone see the problem? Here is my code:

Thanks!

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34656
366

Kevin,
In this code, things are set so that j will always be one more than i at the end of the loop. The problem being in the line with the comment "move it to the front." If j is one higher than i and i is the last element in the array, there's no element there.

Think about what you want to do if the last element is the duplicate. Can you say it in a sentence?

Rob Spoor
Sheriff
Posts: 20545
56
I don't think that's the problem. The thing is, j always points to the last assigned element. That means that the length of the sub array is not j, but j + 1. If I change the for loop guard to "i <= j" I see the 11. If I change A[9] to 13, I see that 13 as well.

Ganesh Gowtham
Ranch Hand
Posts: 225
Hi Kevin ,

let me know your view on the below code .

I think it will easy,simple and uses Util classes .

Rob Spoor
Sheriff
Posts: 20545
56
If you use a LinkedHashSet instead of a HashSet, you preserve the order and that would be a viable solution. It still runs in linear time (O(n)), because the adding of the array (as list) is linear; the check whether or not the element exists takes constant time (O(1)) because of the hashing.

Still, if this were a homework assignment, I doubt you would get much credit for it. I would add it as an addendum to show how easy it can be, but the professor would probably want to see your own algorithm. And that's just what Kevin has done, albeit with a minor bug.

Campbell Ritchie
Sheriff
Posts: 49367
62
Not convinced about the use of a Set, because the output was supposed to be ordered. Also I think he is supposed to work out the algorithm himself.

Ganesh Gowtham
Ranch Hand
Posts: 225
Hi Rob i agree with you regarding the maintaining the order .

Preserving Order

Sorting....

Kevin Behr
Greenhorn
Posts: 23
Hey guys,

Thanks for all of your replies! I greatly appreciate it.

Ganesh: Nice implementation, but unfortunately I can't use it. Campbell is right in that I have to work out the algorithm. The reason being is that I am taking a "Formal Methods and Models" class, in which we derive programs (mathematically). I'm working backwards to understand the problem more (and because I'm awful at math!).

Rob, you were right, by changing the < to a <= in the second for loop, the 11 appeared. I test a couple more sets, and things seem to be working well!

Now that I understand what the program should look like, I have to derive it from a loop invariant that was given to me

Thanks again!

Rob Spoor
Sheriff
Posts: 20545
56
You should actually have done it the other way around. Given a pre condition, post condition and loop invariant, you should be able to write the program.

Could you please tell us what these are? We may be able to help you. We won't give you full solutions though.

Kate Terlecka
Greenhorn
Posts: 12
Hi,

your program calculates everything correctly - it's just that you're not writing the last element to the output. You should write that up to j, not j-1 :

Kate T.