How to get the most common element(s) in an array?

[pcjjdy]

For example: I have an array here: {0,1,2,3,4,0,4} then the output should be {0,4}.

Can anyone help me? .)

[pcjjdy]

anyone?
Help…

[Rrrramadge]

this solves your example problem. hopefully does what you need.

[Rrrramadge]

So if the first array contained integers from 0-100 rather than 0-4?

[anonymous_user_11d28c921 (anonymous_user_11d28c92)]

Assuming your array contains integers, but you can really do this on every datastructure that can be linear sorted.

1. You need a struct S with two values: int key and int count;
2. Make a new (dynamic) array T with the struct as type created in (1)
3. You sort the element array E
4. Then the same elements are grouped together. Create a instance of S and append it to T: The key is the first element in E and count is initialized with 1.
5. Then you increment count as long as you read from E the same value as the key.
   If you come over an element with a different value than your key, you create a new instance of struct S and append to T: key = value of element, count = 1. Then repeat the process 5. until there are no elements left (in E).

Now iterate over T and use a modified max search algorithm to get the key with the highest count.

Example:
{0,3,6,23,4,4,8,6,4,7,6,6}
Sorted: {0,3,4,4,4,6,6,6,7,8,23}
=> T = { {0,1}, {3,1}, {4,3} ,{6,3},{7,1},{8,1},{23,1} }
Modified Max Search:
Create a dynamic array A.
Use a standard max search algorithm, but push the max element into A. Everytime you see a value that is equal to your current max, push it also into A. If you come across a value that is greater than A, remove all elements from A and push the new max elem into A. Repeat.
After that just return A.

Time complexity:
Sorting is dominant here: O(n log n)
Going throught the array and grouping: O(n)
Going through the grouped array (worst case all elements have the same amount of occurance): O(n)
Deleting all elements in Array A: O(n)
So overall you have O(n log n + 3n) = O(n log n). you can reduce the overhead of 3n if you don’t group etc. to n.
Whatever. Here you go.

[anonymous_user_11d28c921 (anonymous_user_11d28c92)]

In the worst case you have a runtime complexity of O(n^2) with that is if NewArray contains the exact same elements as the original array (no duplicates at all.) Also not speaking of the overhead introduced by AddUnique. It’s probably faster for smaller amounts, but for higher 1000+ this will introduce significant perforamcen problems I guess.

[pcjjdy]

Yep,it seems like a kind of way to solve. But I just took an example. What if the length of array is 100 or more?

[Speckulous]

I didn’t test it, but there this should work.

1. Make a new array and delete duplicates (“add unique”)
2. Create an array with zeros, which is the size of the new array (I forgot that in the picture!)
3. For each of those elements in the new Array, check each of your Array Elements, if they are the same (double for loop)
4. If they are the same, increment the according element in the count array
5. Get the index of the max of the count array, this index in the new Array is your searched Element

[Rrrramadge]

That works if you choose to go this way.