This content has been marked as final.
Show 1 reply

1. Re: Finding duplicates in Array
843785 Jul 3, 2008 2:51 AM (in response to 843785)java80 wrote:
You already have achieved b. The integers must be stored somewhere and you don't use any additional storage. The naive approach gives an O(N*N) algoritm but by first sorting you've changed that to an O(N*logN) algoritm which is better
I wrote this test program to find duplicates and now I wonder how can i change my program to follow the above said 2 approaches:
To achieve a. you need to add a data structure namely a set. The algoritm goes,
For all integers in the array {
If the integer is in the set it's a duplicate.
Add the integer to the set.
}
For the set you can use a HashSet or implement your own set using an integer array. It's important that you can check whether an integer is in the set in O(1) time.
Thanks to the set's O(1) behavior the above algoritm will be O(N) and that's the fastest possible. The cost is the set you need.