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

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 | Author of Java 9 Cookbook

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 | My Blog | Author of Java 9 Cookbook

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??

Live Curious!!!

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here