In addition to the usual use of the hashmap, my idea is that if we can tell for sure if a certain number can not be the majority (i.g. if a number show up for the first time after the half is passed), then we disregard to make the scan of the hash quicker.

```
public class Solution {
public int majorityElement(int[] num) {
int n = num.length;
Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();
for(int i = 0; i < n; i++) {
Integer frequency = frequencies.get(num[i]);
int freq = 0;
if (frequency != null)
freq = frequency;
if (freq + (n-i-1) < n/2 && frequency != null) {
frequencies.remove(num[i]);
} else {
frequencies.put(num[i], freq + 1);
}
}
for (Map.Entry<Integer, Integer> entry: frequencies.entrySet()) {
int freq = entry.getValue();
if (freq > n/2) {
return entry.getKey();
}
}
return 0;
}
}
```