Array with specific values

Question

Given an array of size n, where: 1/2 of the array has one (unknown) value. 1/4 of the array has one (unknown) value. And so on for 1/8, 1/16, 1/32 Give an algorithm to sort the array. You cannot use the median search algorithm

So, I realized: There are only logn different values. There is a simple solution using a binary heap on O (n * loglogn). This seems like a question that needs to be solved in O (n)

Answer 1

The idea is to use the Majority algorithm, which takes O (n), and then discovers that a “half” value removes it from the array, and then does it again in the new array n + n / 2 + n / 4 + n / 8 + ..... <2n => O (n)

Answer 2

Here is one possible approach:

• scan arrays and save element frequencies (there are log n individual elements) in a hash table in amortized O (n) time; this is doable because we can do inserts in amortized O (1) time ;
• Now it launches the classic sorting algorithm for these log items n: this is done in deterministic O (log n log log n) time, using, say, heap sorting or merge sorting;
• now expand the sorted array --- or create a new one and fill it with the sorted array and hash table --- using frequencies from the hash table; this can be done in O (n) amortized time.

Thus, the entire algorithm operates in amortized time O (n), i.e. elimination of duplicates and expansion of the sorted array prevail in it. The complexity of the space is O (n).

This is essentially optimal because you need to “touch” all the elements in order to print a sorted array, which means that we have the corresponding Omega (n) lower bound for the runtime.

Answer 3

After going through the array once, save the hash map for visible values. As you said, only log(n) different values ​​exist.

Now you have a list of all the different values ​​- sorting them will take lon(n)*log(log(n))

Once you have sorted uniq, how easy it is to compose the original array: the maximum value will take cells n/2 , the second will take n/4 , etc.

The total runtime of O(n + lon(n)*log(log(n)) + n) , which is O(n)