• Post Reply Bookmark Topic Watch Topic
  • New Topic

Looking for equal longs in an array.  RSS feed

 
Ranch Hand
Posts: 35
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


I have about 100,000 (N) random long variables in an array. I'd like to find if any two longs are equal; they're not expected to be. At this size, should I use the Hashtable or brute force it at a cost of N^2/2?


Thanks,

Chris
 
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What do you want to do; just check if there are any duplicates? What you could do is put them in a Set (for example a HashSet) and check what the size of the set is. If it's less than the number of numbers you put in, there must be duplicates (a Set cannot contain duplicate elements).
 
Chris Kimball
Ranch Hand
Posts: 35
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Yes, any one match is a sufficient outcome.

Is using a HashSet likely to be faster than just checking against previous values looking for a duplicate?

Thanks,

Chris
 
Sheriff
Posts: 22846
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Chris Kimball wrote:Is using a HashSet likely to be faster than just checking against previous values looking for a duplicate?


I don't think those two things are mutually exclusive. Go through the array one entry at a time and add each entry to a HashSet until you find a duplicate or reach the end of the array.
 
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Checking through the array will run in quadratic complexity; entering entries into a HashSet runs in (amortised) constant time, so for the whole array you are looking at linear complexity. Unless the array is very small, you will get much faster execution with the set. Best to give the set an initial capacity equal to the array's length, which will make it faster still.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!