- Randomly pick a number between 0 and n-1, loop over the array to see if this number appears more than n / 3 times. - O (n)
- repeat 1 for 100 times.

Therefore the time complexity is O(100n), which is essentially still O(n).

Suppose we have 2/3 chance to miss a desired number in one pick, the possibility of missing this number in 100 picks would be (2/3)^100, which is 10E-18. This possibility is so low, maybe even lower than the possibility of leetcode server crash in the next second.

So I guess this solution is sufficiently reliable. If not, we could repeat step 1 for 1000 times, to make sure finding out the two numbers.

Moreover, this solution could be generated to solve questions like "find all elements that appear more than n/m times."

```
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> output = new ArrayList<>();
for (int i = 0; i < 100; i += 1) {
int count = 0;
int index = (int)(nums.length * Math.random());
for (int j = 0; j < nums.length; j += 1)
if (nums[index] == nums[j])
count += 1;
if (count > nums.length / 3 && !output.contains(nums[index]))
output.add(nums[index]);
}
return output;
}
}
```