今天的力扣每日一题：
398. 随机数索引 - 力扣（LeetCode） (leetcode-cn.com)
给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。
实现 Solution 类：
Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。
示例：
输入
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
输出
[null, 4, 0, 2]
解释
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
看到这道题我首先想到的就是哈希表，于是就有了如下代码：
class Solution {
int size;
Random random ;
Map> map;
public Solution(int[] nums) {
size = 0;
random = new Random();
map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
if(map.containsKey(nums[i])){
map.get(nums[i]).add(size++);
}else{
List list = new ArrayList<>();
list.add(size++);
map.put(nums[i],list);
}
}
}
public int pick(int target) {
List arr = map.get(target);
return arr.get(random.nextInt(arr.size()));
}
}
不难看出，这样的算法适合数组已经固定的情况下，如果数组是以流的方式给出来的，那么该怎么解这道题呢。这样就需要用到我们的蓄水池抽样算法了。
蓄水池抽样算法主要可以解决这类的问题：总的样本数量未知，从所有样本中抽取若干个，要求每个样本被抽到的概率相等。
思路：从前往后处理每个样本，每个样本成为答案的概率为1/k，其中k为样本编号（编号从1开始），最终可以确保每个样本成为答案的概率均为 1/n（其中n为样本总数）。
具体思路：从前往后处理每个节点，同时记录当前节点的编号，当处理到节点k时，在[0,k)范围内进行随机，若随机到结果为0（发生概率为1/k ），则将节点 k的值存入答案，最后一次覆盖答案的节点即为本次抽样结果。
Java代码实现：
class Solution {
int[] arr;
Random random;
public Solution(int[] nums) {
random = new Random();
arr = new int[nums.length];
for(int i = 0 ;i < nums.length;i++){
arr[i] = nums[i];
}
}
public int pick(int target) {
int res = 0;
for(int i = 0,cnt = 0;i < arr.length;i++){
if(arr[i] == target && random.nextInt(++cnt) == 0){
res = i;
}
}
return res;
}
}
c++代码实现：
class Solution {
int[] arr;
Random random;
public Solution(int[] nums) {
random = new Random();
arr = new int[nums.length];
for(int i = 0 ;i < nums.length;i++){
arr[i] = nums[i];
}
}
public int pick(int target) {
int res = 0;
for(int i = 0,cnt = 0;i < arr.length;i++){
if(arr[i] == target && random.nextInt(++cnt) == 0){
res = i;
}
}
return res;
}
}
经过了这道题，在看另外一道题382. 链表随机节点 - 力扣（LeetCode） (leetcode-cn.com)
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例：
输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]
解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。
这道题符合抽样算法，我们不知道具体节点的个数，从所有样本中随机抽取，与上道题不一样的是上一道题是有一个target，符合target才将对应的下标纳入到随机的范围，这道题则是所有的节点都是随机的范围。
思路：我们每处理玩一个节点，就进行随机，如果随机之后的值为0，就将当前节点的值作为返回值，直到遍历结束
Java代码：
class Solution {
Random random;
ListNode head;
public Solution(ListNode h) {
random = new Random();
head = h;
}
public int getRandom() {
int res = 0,cnt = 0;
ListNode temp = head;
while(temp != null){
if(random.nextInt(++cnt) == 0){
res = temp.val;
}
temp = temp.next;
}
return res;
}
}
C++代码：
class Solution {
public:
ListNode * head;
Solution(ListNode* _head) {
srand((unsigned) time (nullptr));
head = _head;
}
int getRandom() {
int res = 0,cnt = 0;
ListNode* temp = head;
while(temp != nullptr){
if(rand() % ++cnt == 0){
res = temp->val;
}
temp = temp->next;
}
return res;
}
};
