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

By | March 27, 2017 | 1,077 Views

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){
}
}

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:

This site uses Akismet to reduce spam. Learn how your comment data is processed.