Formatted question description:

 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.

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


 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.

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


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.



import java.util.Random;

public class Random_Pick_Index {

    // ref:
    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) {


                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