It reminds me of a frequent pattern mining algorithm I've implemented before (Apriori). I just adapt the concept there and form a straight-forward code:

First, counting frequency for each num, using a HashMap -- O(n)

Second, finding largest frequency -- O(n)

Finally, finding the "num" associated with the largest frequency found in previous step. -- O(n)

It's not the best solution but it seems straightforward to me. Feel free to improve it...

```
public int majorityElement(int[] num) {
HashMap<Integer, Integer> frequency = new HashMap<>();
for (int i = 0; i < num.length; i++) {
if (frequency.containsKey(num[i])) {
int currentFreq = frequency.get(num[i]);
currentFreq++;
frequency.put(num[i], currentFreq);
} else {
frequency.put(num[i], 1);
}
}
Integer largest = Integer.MIN_VALUE;
for (java.util.Map.Entry<Integer, Integer> current : frequency.entrySet()) {
Integer currentFreq = current.getValue();
if (currentFreq > largest) {
largest = currentFreq;
}
}
Integer resultKey = Integer.MIN_VALUE;
for (java.util.Map.Entry<Integer, Integer> current : frequency.entrySet()) {
if (current.getValue().equals(largest)) {
resultKey = current.getKey();
}
}
return resultKey;
}
```

--- oh by the way this solution doesn't care about the [n/2] constraint given by the question... :(