Source url: https://leetcode.com/problems/majority-element/
Given an array of size n, find the majority element. The majority element is the element that appears more than
⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exists in the array.
We provide 3 solutions. Hash-map approach, divide and conquer approach and sort approach.
This solution is easily understood, we use a hash-map to store counts of elements. The first loop we count every element. The second loop we find the most frequency element, it is our result. Actually, we can use one loop to get the result, a little faster, but it will not change the complexity, so we ignore it.
Divide and conquer approach
Because the majority element appears more than half times, so we know if we split the array to left and right, it will be one of the majority element in left or right. So we can use divide and conquer approach, cut again and again until only one element, just Mergesort problem.
First, we sort the array, then one loop to count elements. (And there are a more easy solution, sort and get the middle element, it must be the majority element.)
Github address: https://github.com/tinyfool/leetcode/tree/master/src/p0169
Want to know details of the Divide and conquer, check my post: Leetcode problems of Divide and conquer.