aspose file tools*
The moose likes Java in General and the fly likes Removing dups from array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Removing dups from array" Watch "Removing dups from array" New topic
Author

Removing dups from array

Kevin Behr
Greenhorn

Joined: Jun 29, 2006
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

Joined: May 26, 2003
Posts: 30764
    
156


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?


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Ganesh Gowtham
Ranch Hand

Joined: Mar 30, 2005
Posts: 225

Hi Kevin ,

let me know your view on the below code .



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


Thanks, Ganesh Gowtham
http://ganesh.gowtham.googlepages.com
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

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

Joined: Oct 13, 2005
Posts: 39418
    
  28
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

Joined: Mar 30, 2005
Posts: 225

Hi Rob i agree with you regarding the maintaining the order .

Preserving Order



Sorting....

Kevin Behr
Greenhorn

Joined: Jun 29, 2006
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

Joined: Oct 27, 2005
Posts: 19720
    
  20

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

Joined: May 13, 2009
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.


--
Never argue with an idiot.
He will bring you down to his level
and beat you with experience.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Removing dups from array