Feb. 21, 2014, 4:22 p.m. by Rosalind Team
Topics: Sorting
An array
Given: A positive integer
Return: For each array, output an element of this array occurring strictly more than
Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.
4 8 5 5 5 5 5 5 5 5 8 7 7 7 1 7 3 7 7 1 6 5 10 100 1000 1 5 1 6 7 1 1 10 1
5 7 -1 -1
Discussion
It is not difficult to develop a divide-and-conquer algorithm checking whether a given array of size
$n$ contains a majority element in$O(n \log n)$ time. It is interesting to note that there is also a linear time algorithm and it is also based on divide-and-conquer.