• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Removing dups from array

 
Kevin Behr
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 34218
341
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Pie
Posts: 20512
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IBM DB2 Eclipse IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Kevin ,

let me know your view on the below code .



I think it will easy,simple and uses Util classes .
 
Rob Spoor
Sheriff
Pie
Posts: 20512
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IBM DB2 Eclipse IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Rob i agree with you regarding the maintaining the order .

Preserving Order



Sorting....

 
Kevin Behr
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20512
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic