Java random number solution

  • 6
    1. 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)
    2. 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]))
                return output;

  • 4

    Very creative idea!! But frankly speaking, the methods we write in Leetcode are basic/fundamental level methods, which could be called billions of time when the software is running. For example, during a 3D game is running, the math function Math.sqrt may be used almost millions of time every minute, one wrong answer could lead to disastrous result. So although your solution passed OJ, I am afraid it's stil flawed.

  • 0

    That's true. This solution is never going to be absolutely correct. Plus, it takes longer than O(n^2) time for n < 100.

    However, maybe I should emphasize the 2e-18 error possibility. That is, if this method is called a million times per second, wrong answer occurs every 10,000 years!

    Maybe it is still not enough. How about increase number of times in step 2 to 150? Wrong answer occurs every 8,000,000,000,000 years - 500 times the age of universe...

  • 0

    Make sense!! Everything is a balance of cost and reliability including algorithms. When reliability is good enough, we need to try best to lower cost. I now think a 2e-18 possibility is good enough.

  • 0
    This post is deleted!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.