Clean, understandable, O(1) momery, O(n) time, JAVA solution


  • 14
    L
    public class Solution {
        int[] nums;
        Random rand;
        public Solution(int[] nums) {
            this.nums = nums;
            this.rand = new Random();
        }
        public int pick(int target) {
            int total = 0;
            int res = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
                    // randomly select an int from 0 to the nums of target. If x equals 0, set the res as the current index. The probability is always 1/nums for the latest appeared number. For example, 1 for 1st num, 1/2 for 2nd num, 1/3 for 3nd num (1/2 * 2/3 for each of the first 2 nums).
                    int x = rand.nextInt(++total); 
                    res = x == 0 ? i : res;
                }
            }
            return res;
        }
    }
    

  • -2

    @lycjava
    Sorry, you answer is not random! Although you program has been passed.
    Because, the probability of "x==0" becomes less when total
    becomes more and more larger.In fact, its probality becomes more and
    more less! The index returned by function is more likely the last index of target!

    you can run you programs, then look the results!


  • 3
    L

    @sa1velet Thank you for your reply.

    Of course the probability of x == 0 is less and less, which is the basic theory that each item enjoys the same probability. Think about it. For the 4th item, probability of x == 0 is 0.25, therefore, the probability of the last item is 0.25. The probability for the previous items are respectively 11/22/33/4=1/4, 1/22/33/4, and 2/33/4....

    I wonder whether you had the change to take probability course. If not, please study a little that would be helpful: https://en.wikipedia.org/wiki/Conditional_probability.


  • 0
    P

    Awesome implementation!
    Similar idea as Fisher-Yates Shuffle, for random select.
    Could be better if you could explain the conditional probability part more clearly.


  • 0
    5
    This post is deleted!

  • 0

    @wave Not really, the earlier ones has larger probability to be chosen when i is on it although later it had larger probability to be replaced by later ones. But it turns out each one has the same probability of being selected. Check out RESERVOIR SAMPLING!!


  • 0
    G
    public class Solution {
        int[] nums;
        Random rand;
        public Solution(int[] nums) {
            this.nums = nums;
            this.rand = new Random();
        }
        public int pick(int target) {
            int total = 0;
            int res = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
             
                    int x = rand.nextInt(++total); 
                    if(x ==0) res = i;
                    res = x==(total+1) ? i : res;
                    //res = x == 0 ? i : res;
                    System.out.println(x+ " " +res);
                }
            }
            return res;
        }
    }
    

    Had a lot of trouble finding why when res = x==0 ? i : res;
    As it makes more sense that if the last value of x be conisdered for i... just a random thought.
    Hope may help someone


  • 0
    C

    Smart idea! Thanks for sharing.


Log in to reply
 

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