Interview Q: How to Find the Most Popular Number in a Sorted Array
1 answer
I would do it with a similar approach like binary search.
I would first find the values ββof 8 numbers, which would be at 0/8, 1/8, 2/8 ... 8/8 of the array. The same numbers that you find when you binary search for something.
Since the same number must be n / 4 the size of the array or greater, it must reach at least two of these bounds per line. Like a number, 2/8 and 3/8 are the same.
Therefore, this identification of the number and the partial position is performed at a constant time.
Then you just keep finding where it starts and where it ends, which is a typical binary search.
Complexity: O(log n)
+2
source to share