Give a linear-time algorithm that determines whether an unsorted sequence of n real numbers contains a number that occurs at least n/4 times in the sequence. You algorithm should report “no” if no such number exist; otherwise, it should report all numbers occurring at least n/4 times. Argue about the correctness of your algorithm. Assume that Select works also when the elements are not distinct.
The select algorithm is https://en.wikipedia.org/wiki/Selection_algorithm
It seems pretty easy to get O(nlogn), but I can't seem to figure out how to get it done in linear time. The last line would imply that I need to use select but I can't seem to figure out how that's helpful. If someone could push me in the right direction that would be very helpful.
Assume there is an integer $d$ with $\frac n5<d\le\frac n4$ (this assumtion hoilds at least for $n\ge 20$ because that makes $\frac n4-\frac n5\ge1$; by inspection it holds for all $n$ except $1,2,3,5,6,7,10,11,15$; you can us a "brute force" method for these small $n$). Select the $k$th largest element for $k\in\{d,2d,3d,4d\}$. Then any number occuring at least $\frac n4$ times occurs among these four numbers. For each of them (after removing duplicates) scan through the list to count their occurances.