Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Find two repeating elements in an Array  RSS feed

 
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)

 
author
Posts: 23811
140
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Bartender
Posts: 3185
34
Google App Engine Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 47
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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...??
 
Mohamed Sanaulla
Bartender
Posts: 3185
34
Google App Engine Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did you try running the program? let us know the results and if it holds good for different inputs.
 
Sagar Dabas
Ranch Hand
Posts: 47
C++ Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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??
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 227
Eclipse IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!