GeeCON Prague 2014*
The moose likes Beginning Java and the fly likes Missing numbers from sorted list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Missing numbers from sorted list" Watch "Missing numbers from sorted list" New topic
Author

Missing numbers from sorted list

divya madala
Ranch Hand

Joined: Jan 10, 2001
Posts: 61
Which collections object is good to show the missing number from a sorted list. Any ideas please!!!
Suppose my numbers are
100234
100235
100237
100238
Then the output should be 100246
[ February 16, 2004: Message edited by: divya madala ]
Tom Blough
Ranch Hand

Joined: Jul 31, 2003
Posts: 263
Look at the abstract Map class. A HashMap would probably work fine for your application.
Tom Blough
[ February 16, 2004: Message edited by: Tom Blough ]

Tom Blough<br /> <blockquote><font size="1" face="Verdana, Arial">quote:</font><hr>Cum catapultae proscriptae erunt tum soli proscripti catapultas habebunt.<hr></blockquote>
Angel Dobbs-Sciortino
Ranch Hand

Joined: Sep 10, 2003
Posts: 101
If you use a TreeSet of Integer objects, it will sort the numbers for you. Then you can use an Iterator to step through the Set, and subtract the current number from the previous number to find out if it skipped a number or not.
Angel
[ February 16, 2004: Message edited by: Angel Dobbs-Sciortino ]
Nils Hofmann
Greenhorn

Joined: Jan 10, 2004
Posts: 9
hi,
it's a bit circuitous, but you can try the following. set up a second list (called newList)
with all possible numbers. when you call newList.removeAll(oldList) then in newList remain
only that numbers, which are not in oldList.
example:

nils
[ February 17, 2004: Message edited by: Nils Hofmann ]
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
it's a bit circuitous, but you can try the following. set up a second list (called newList) with all possible numbers.
Wouldn't that be a very big list? In fact, wouldn't it be an infinitely big list?


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Wouldn't that be a very big list? In fact, wouldn't it be an infinitely big list?
True. But since the list has already been sorted it's easy to find the smallest and largest number in the list; you can restrict things that way.
Even so, it seems a bit unnecessary to list all numbers in the range first. I'd just loop through the sorted list, comparing each element to the previous element. If the difference is greater than 1, you've got some missing numbers and ought to be able to determine what they are. Add them to the list of missing numbers, and continue looping through the original list.
Note that in this strategy, you will have to be a little careful at the beginning and end of the list, to make sure you don't accidentally refer to elements that don't exist. You may have to adjust the initial and exit conditions of the loop; they're not quite what you're used to seeing.


"I'm not back." - Bill Harding, Twister
 
Don't get me started about those stupid light bulbs.
 
subject: Missing numbers from sorted list