本文主要是介绍398. Random Pick Index 382. Linked List Random Node 蓄水池原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓄水池原理应用：
随机返回n个元素中的某个元素，从0开始遍历这n个元素 用count记录遍历过得元素数目（符合要求的元素在数，比如数值等于target的数组索引），如果random(count)==0 则选中这个元素。 可以证明 在遍历的过程中 随着遍历元素数目的增加 random（count）==0 的几率是随机均等的
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); 蓄水池问题：
随机产生一个 索引 其值等于给定的target。 等于target的索引有很多 需要随机
关键 产生一个随机数[0,count) 范围内的随机数如果这个数等于0 则选中该索引值。（在[0,count)范围内产生一个值等于0的概率为1/count） 一共有count个符合条件的数
public class Solution {int []nums;Random ran;public Solution(int[] nums) {this.nums=nums;this.ran=new Random();}public int pick(int target) {int count=0;int result=0;for(int i=0;i<nums.length;i++){if(target!=nums[i])continue;if(ran.nextInt(++count)==0)result =i;}return result;}
}随机返回链表中的一个节点：
public class Solution {ListNode head;/** @param head The linked list's head.Note that the head is guaranteed to be not null, so it contains at least one node. */public Solution(ListNode head) {this.head=head;}/** Returns a random node's value. */public int getRandom() {Random ran=new Random();ListNode dummy=head;int result=0;// ListNode dummy=null;for(int i=1;dummy!=null;i++){if(ran.nextInt(i)==0)result=dummy.val;dummy=dummy.next;}// return dummy.val;return result;}
}这篇关于398. Random Pick Index 382. Linked List Random Node 蓄水池原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
