How to efficiently gather the repeating elements in a given array?

user_8007116 0
Viewed 54

I'd like to gather the duplicates in a given array. For example, i have an array like this:

{1,5,3,1,5,6,3}

and i want the result to be:

{3,3,1,1,5,5,6}

In my case, the number of cluster is unknowen before calculation, and the order is not concerned.

I achived this by using the bult-in function Sort in C++. However, actually the ordering is not necessary. Hence, i guess there are probably more efficient methods to accomplish it.

Thanks in advance.

function algorithm c++
1 Answers

First, construct a histogram noting frequencies of each number. You can use a dictionary to accomplish this in O(n) time and space.

Next, loop over the dictionary's keys (order is unimportant here) and for each one, write a number of instances of that key equal to the corresponding value.

Example:

{1,5,3,1,5,6,3}                  input
{1->2,5->2,3->2,6->1}            histogram dictionary
{1,1,5,5,3,3,6}                  wrote two 1s, two 5s, two 3s, then one 6

This whole thing is O(n) time and space. Certainly you can't do better than O(n) time. Whether you can do better than O(n) space or not while maintaining O(n) time I cannot say.

user_8472690
Related