wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Find two repeating elements in an Array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Find two repeating elements in an Array" Watch "Find two repeating elements in an Array" New topic
Author

Find two repeating elements in an Array

Raihan Jamal
Ranch Hand

Joined: Mar 23, 2010
Posts: 86
This code works fine. But it is O(n^2) complexity. Is there any other efficient way to do this. I want to do it in O(n) or O(log n)

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18757
    
  40

Raihan Jamal wrote:This code works fine. But it is O(n^2) complexity. Is there any other efficient way to do this. I want to do it in O(n) or O(log n)




Keep in mind that a lower order doesn't mean that it is faster. It just means that it scales better.

So, if you want a lower order, you can actually move the data into a collection first. For example, if you simply add each element into a hashmap, but check if the element is already in the hashmap first (if the put() method returns null or not), then I can get it much lower.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Mohamed Sanaulla
Saloon Keeper

Joined: Sep 08, 2007
Posts: 3068
    
  33

i like Henry's approach. you can populate the elements in the Hashmap- the key would be array element and the value will be number of times its repeating.
analysing the efficiency would be O(n) to loop through the list, O(1) to fetch element from Hashmap. so effectively it would be O(n). And then another loop to fetch the keys from the Hashmap.


Mohamed Sanaulla | My Blog
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

Mohamed Sanaulla wrote:i like Henry's approach. you can populate the elements in the Hashmap- the key would be array element and the value will be number of times its repeating.
analysing the efficiency would be O(n) to loop through the list, O(1) to fetch element from Hashmap. so effectively it would be O(n). And then another loop to fetch the keys from the Hashmap.


Am i on the right track...??


Live Curious!!!
Mohamed Sanaulla
Saloon Keeper

Joined: Sep 08, 2007
Posts: 3068
    
  33

Did you try running the program? let us know the results and if it holds good for different inputs.
Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

Mohamed Sanaulla wrote:Did you try running the program? let us know the results and if it holds good for different inputs.


Integer[] a = {1,2,3,3,0,1,5,1,1};
run:
1 repeats : 4
3 repeats : 2

Integer[] a = {1,2,3,4,0,1,5,2,1};
run:
1 repeats : 3
2 repeats : 2

Yes,it is working. Is it's efficiency O(n)??

Is containsKey(x) function not increasing the complexity??
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7696
    
  20

Sagar Dabas wrote:Yes,it is working. Is it's efficiency O(n)??

Is containsKey(x) function not increasing the complexity??

Yes, and so are the map.get() and map.put(), not to mention the final iteration to check occurrence values; but they aren't changing the behaviour of the algorithm with relation to time.

Big O notation is an indication of scalability, not of elapse time; so if a program has O(n) characteristics, if it takes time T to execute when n=1, it will take time 10T when n=10. But that says nothing about how big (or long) T actually is.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Aditya Jha
Ranch Hand

Joined: Aug 25, 2003
Posts: 227

If you're interested in finding repeated element(s) only (and not how many times they have repeated), you can do the following:
Just as a side note - at the end, the set will have only unique elements from the array.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Find two repeating elements in an Array