# leetcode398. 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);```

## 思路一：O(2n)的实现

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

public int pick(int target) {
int count = 0;
int result = -1;
for(int i = 0 ; i<nums.length ; i++) {
if(target == nums[i]) {
count++;
}
}
int index = r.nextInt(count);
for(int i = 0 ; i<nums.length ; i++) {
if(target == nums[i]) {
index--;

if(index == -1){
result = i;
break;
}
}
}
return result;
}```

## 思路二：蓄水池问题

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

public int pick(int target) {
int count = 0;
int result = -1;
for(int i = 0 ; i<nums.length ; i++) {
if(nums[i] == target) {
int index = r.nextInt(++count);
if(index == 0) {
result = i;
}
}
}
return result;
}```

0 条评论

• ### leetcode442. Find All Duplicates in an Array

存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。

• ### leetcode473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchstic...

• ### leetcode448. Find All Numbers Disappeared in an Array

假设一个长度为n的整数数组，数组中的元素的值位于[1,n]区间中。问，该数组中有哪些[1,n]区间中的整数没有出现？

• ### Leetcode 26. Remove Duplicates from Sorted Array

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....

• ### Leetcode 747. Largest Number At Least Twice of Others

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....

• ### leecode刷题（8）-- 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

• ### leetcode442. Find All Duplicates in an Array

存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。