```
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
populate(nums, 0, nums.length - 1, result);
return result;
}
void populate(int []nums, int begin, int end, List<Integer> result) {
int freq = nums.length / 3;
if(result.size() == 2)
return;
int[] range = partition(nums, begin, end);
if(range == null)
return;
if(range[1] - range[0] + 1 > freq)
result.add(nums[range[0]]);
if(range[0] - begin > freq)
populate(nums, begin, range[0] - 1, result);
if(end - range[1] > freq)
populate(nums, range[1] + 1, end, result);
}
int[] partition(int[] arr, int begin, int end) {
if(begin > end)
return null;
int pivot = arr[end];
int i = begin;
for (int cur = begin; cur < end; cur++) {
if (arr[cur] < pivot) {
swap(arr, i, cur);
i++;
}
}
swap(arr, i, end);
int j = i;
for (int cur = i + 1; cur <= end; cur++) {
if (arr[cur] == arr[i]) {
swap(arr, j + 1, cur);
j++;
}
}
return new int[] { i, j };
}
void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```

Explanation:

- Partition the array into 3 parts (instead of normal 2 parts that is used for QuickSort, etc). Part 1 has all the numbers less than pivot, part 2 has all the number equal to pivot and part 3 has all the numbers greater than pivot
- If length of part2 is greater than n/3, we add that element.
- Now, recursively call partition of part1 and part3 only if its size is greater than n/3

I think this solution can be generalized to get all the numbers with more than n/k occurrences for any given k.

This solution does pass all the test cases. However, I am not sure if it is indeed a linear time solution as well. Would appreciate comments on its running time.