@@ -0,0 +1,1775 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.Random;%0A%0A/**%0A * Given an array of integers with possible duplicates, randomly output the index of a given target number. You can%0A * assume that the given target number must exist in the array.%0A * %3Cp%3E%0A * Note:%0A * The array size can be very large. Solution that uses too much extra space will not pass the judge.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * int%5B%5D nums = new int%5B%5D %7B1,2,3,3,3%7D;%0A * Solution solution = new Solution(nums);%0A * %3Cp%3E%0A * // pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.%0A * solution.pick(3);%0A * %3Cp%3E%0A * // pick(1) should return 0. Since in the array only nums%5B0%5D is equal to 1.%0A * solution.pick(1);%0A * %3Cp%3E%0A * Tags: Reservoir Sampling%0A * Similar Problems: (M) Linked List Random Node%0A */%0Apublic class RandomPickIndex %7B%0A%0A    /**%0A     * Your Solution object will be instantiated and called as such:%0A     * Solution obj = new Solution(nums);%0A     * int param_1 = obj.pick(target);%0A     */%0A    class Solution %7B%0A%0A        private final int%5B%5D nums;%0A        private final Random r;%0A%0A        public Solution(int%5B%5D nums) %7B%0A            this.nums = nums;%0A            r = new Random();%0A        %7D%0A%0A        /**%0A         * Reservoir Sampling.%0A         * Keep a count for the target number.%0A         * Replace index with 1 / count probability.%0A         */%0A        public int pick(int target) %7B%0A            int count = 0;%0A            int index = 0;%0A            for (int i = 0; i %3C nums.length; i++) %7B%0A                if (nums%5Bi%5D == target) %7B%0A                    count++;%0A                    if (r.nextInt(count) == 0) %7B%0A                        index = i;%0A                    %7D%0A                %7D%0A            %7D%0A            return index;%0A        %7D%0A    %7D%0A%7D%0A%0A

add Random Pick Index