# Majority Number III

## Problem

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

## Example

Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

## Note

There is only one majority number in the array.

## Challenge

O(n) time and O(k) extra space

## Code - Java

public class Solution {
/**
* @param nums: A list of integers
* @param k:    As described
* @return: The majority number
*/
public int majorityNumber(ArrayList<Integer> nums, int k) {
Map<Integer, Integer> cntMap = new HashMap<>();

for (int n : nums) {
if (cntMap.containsKey(n)) {
cntMap.put(n, cntMap.get(n) + 1);
} else {
cntMap.put(n, 1);
}

if (cntMap.keySet().size() >= k) {
List<Integer> removeList = new ArrayList<>();
for (int key : cntMap.keySet()) {
int cnt = cntMap.get(key);
if (cnt == 1) {
} else {
cntMap.put(key, cnt - 1);
}
}

for (int key : removeList) {
cntMap.remove(key);
}
}
}

Map<Integer, Integer> newMap = new HashMap<>();

int max = 0, maxKey = 0;
for (int key : cntMap.keySet()) {
newMap.put(key, 0);
}

for (int num : nums) {
if (newMap.containsKey(num)) {
int cnt = newMap.get(num) + 1;
newMap.put(num, cnt);
if (max < cnt) {
max = cnt;
maxKey = num;
}
}
}

return maxKey;
}
}