Similarly, original Boyer-Moore Majority Vote Algorithm defined “Majority element of an array A[1 … n]: An array is said to have a majority element if more than half of its entries are the same.” In other words, the majority element is the element that appears more than ⌊ n/2 ⌋. One difference is finding more than one majority element.

## Some History Solutions.

Suppose that A array: int [] A = {3, 2, 2, 4, 4, 1, 7, 4, 2, 4}; Therefore, output should be: 4

### 1. Runtime: O(n), Space: O(n) — Hash table.

Maintain a hash table of the counts of each element,then find the most common one.

public List<Integer> majorityElement(int[] nums) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i: nums){ if(map.containsKey(i)){ map.put(i, map.get(i)+1); }else{ map.put(i, 1); } } List<Integer> result = new ArrayList<Integer>(); for(Map.Entry<Integer, Integer> entry: map.entrySet()){ if(entry.getValue() > nums.length/2){ result.add(entry.getKey()); } } return result; }

### 2. Linear Time Majority Vote Algorithm.

Runtime O(n) time O(1) space.

public int majorityElement(int[] nums) { int result = 0, count = 0; for(int i = 0; i<nums.length; i++ ) { if(count == 0){ result = nums[ i ]; count = 1; }else if(result == nums[i]){ count++; }else{ count--; } } return result; }

### 3. Runtime O(n log n).

Divide and conquer, Sorting array first solution to find a majority element are best implementation.

## Tentative solution.

Thanks to finding the majority element, we temporarily pick up HashMap solution to resolve the problem. N/K= threshold to filter all elements that occur more than N/K times. It is simple to implement but take much space.

int [] A = {3, 2, 2, 4, 4, 1, 7, 4, 2, 4}; Therefore, output should be: {2, 4} if K = 2;

Moreover, an useful reference from algorithms.tutorialhorizon.com improved with datastruct and performance.

**References:**

- Algorithms – Notes on divide and conquer, Prof. Alvarez. Accessed at http://cs.bc.edu/~alvarez/Algorithms/. on 28th Mar 2018.
- GitHub https://github.com/piyush-g/leetcode/blob/master/MajorityElementUnsortedArray.java on 28th Mar 2018
- O(n) time O(1) space fastest solution, Accessed at https://discuss.leetcode.com/topic/8692/o-n-time-o-1-space-fastest-solution on 28th Mar 2018
- LeetCode – Majority Element (Java), Accessed at http://www.programcreek.com/2014/02/leetcode-majority-element-java/ on 28th Mar 2018
- LeetCode – Majority Element II (Java), Accessed at http://www.programcreek.com/2014/07/leetcode-majority-element-ii-java/ on 28th Mar 2018
- Google Interview Question for Software Engineers, Accessed at https://www.careercup.com/question?id=5669183904808960