Question

Formatted question description: https://leetcode.ca/all/398.html

 398	Random Pick Index

 Given an array of integers with possible duplicates,
 randomly output the index of a given target number.

 You can assume that the given target number must exist in the array.

 Note:
 The array size can be very large. Solution that uses too much extra space will not pass the judge.

 Example:

 int[] nums = new int[] {1,2,3,3,3};
 Solution solution = new Solution(nums);

 // pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
 solution.pick(3);

 // pick(1) should return 0. Since in the array only nums[0] is equal to 1.
 solution.pick(1);

Algorithm

Define two variables, counter cnt and return result res.

Traverse the entire array,

• If the value of the array is not equal to target, skip directly;
• If it is equal to target, the counter is increased by 1,

Then we randomly generate a number in the range of [0,cnt). If this number is 0, we assign res.

Code

Java

import java.util.Random;

public class Random_Pick_Index {

    // ref: https://leetcode.com/problems/random-pick-index/discuss/88072/Simple-Reservoir-Sampling-solution
    class Solution {

        int[] nums;
        Random rnd;

        public Solution(int[] nums) {
            this.nums = nums;
            this.rnd = new Random();
        }


        public int pick(int target) {

            int resultIndex = -1;
            int count = 0;

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != target) {
                    continue;
                }

                count++;

                if (rnd.nextInt(count) == 0) {
                    resultIndex = i;
                    // first time nextInt is always 0, so set as first index
                    // for the rest, probobility issue
                }
            }

            return resultIndex;
        }
    }

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */
}

All Problems

All Solutions