Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number

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
Post Views: 110