Algorithm to find majority element
Not what you're looking for? Search our solutions OR ask your own Custom question.
Let A be an array of n elements. An element x is said to be a majority element in A if it occurs in A more than n/2 times. Assume that the only comparisons allowed between elements are tests of equality. Give an algorithm that uses no more than 2n comparisons to determine whether the array A contains a majority element and, if so, find it.
© BrainMass Inc. brainmass.com December 24, 2021, 5:42 pm ad1c9bdddfhttps://brainmass.com/computer-science/arrays/algorithm-to-find-majority-element-63442
Solution Preview
Soln 1.
If there is a majority element, it must be the median. So use the average-time RANDOMIZED-SELECT algorithm (RANDOMIZED-SELECT finds any ith order statistic in linear time, and the median is simply the "middle" order statistic) to find a candidate majority ...
Solution Summary
An Algorithm to find majority element is featured.
$2.49