Page 1 of 1
3. Majority Element. We say an array of elements has a majority element if more than half of its entries are the same. G
Posted: Tue Jul 12, 2022 8:05 am
by answerhappygod
- 3 Majority Element We Say An Array Of Elements Has A Majority Element If More Than Half Of Its Entries Are The Same G 1 (347.32 KiB) Viewed 90 times
3. Majority Element. We say an array of elements has a majority element if more than half of its entries are the same. Given an array with n entries in arbitrary order, design an algorithm to tell whether it has a majority element. If so, return the value of that element. If not, return "NO". Your algorithm should run in O(n log(n)) worst case time. Note that the objects in the array may not be ordered (e.g., they may not be numbers) so you cannot make any comparison of the form of "A
≥ A[j]". However, you can answer queries of the form "A A[j]" in constant time. =