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:
My output is:
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:
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?
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 to 13, I see that 13 as well.
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.
Hi Rob i agree with you regarding the maintaining the order .
Joined: Jun 29, 2006
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