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);
Solution 1： With O(n) Space complexity
- 用Reservoir Sampling的方法来找随机数。
- Create an arraylist to store all index of target, and count total.
- Then use random from [0,total), to equally pick any element in the array
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
total++;
list.add(i);
}
}
res = list.get(rand.nextInt(total)); //int in [0,total)
Solution 2： With O(1) Space complexity
- For each number, if it is equal to target,
count ++and - (Reservoir Sampling) update by 1/total in the loop
random.nextInt(count)指在[0,count)之间随机地选取一个整数。代码中不一定要r==count-1，其实可以写成 r==0，因为只要保证当前概率是 1/count 即可
class Solution {
int[] orginNum;
public Solution(int[] nums) {
orginNum = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
orginNum[i] = nums[i];
}
}
public int pick(int target) {
int count = 0;
int result = 0;
Random rand = new Random ();
for (int i = 0; i < orginNum.length; i++) {
if (orginNum[i] == target) {
count ++;
if (rand.nextInt (count) == 0) {
result = i;
}
}
}
return result;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/
