LeetCode题练习与总结：随机数索引--398

一、题目描述

给你一个可能含有 重复元素 的整数数组 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 之一。每个索引的返回概率应该相等。

提示：

1 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
target 是 nums 中的一个整数
最多调用 pick 函数 10^4 次

二、解题思路

这个问题可以通过水塘抽样（Reservoir Sampling）算法来解决。水塘抽样是一种随机选择算法，用于从n个元素中随机选择k个元素，每个元素被选中的概率相等。

对于这个问题，我们需要从数组 nums 中随机选择一个等于 target 的索引。以下是解题步骤：

遍历数组 nums，记录目标值 target 出现的次数，以及最后一个出现的位置。
在遍历过程中，对于每个等于 target 的元素，以 1/i 的概率选择当前索引，其中 i 是当前元素是第几个等于 target 的元素。
遍历完成后，返回最终选择的索引。

三、具体代码

import java.util.Random;class Solution {private int[] nums;private Random random;public Solution(int[] nums) {this.nums = nums;this.random = new Random();}public int pick(int target) {int count = 0; // 记录target出现的次数int res = 0; // 最终选择的索引for (int i = 0; i < nums.length; i++) {if (nums[i] == target) {count++;// 以1/count的概率选择当前索引if (random.nextInt(count) == 0) {res = i;}}}return res;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(nums);* int param_1 = obj.pick(target);*/

在这个实现中，我们使用了一个 Random 对象来生成随机数。在 pick 方法中，我们遍历数组 nums，每次遇到 target 时，我们计算 random.nextInt(count)，如果结果为0，我们就更新 res 为当前的索引 i。这样，每个等于 target 的索引都有相同的概率被选中。

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化构造函数 Solution(int[] nums)：这个函数只是将输入数组 nums 的引用赋值给类的成员变量，并初始化一个 Random 对象，所以这个操作的时间复杂度是 O(1)。
pick(int target) 方法：这个方法中有一个循环，它遍历了整个数组 nums 一次。在循环内部，对于每个元素，我们进行常数时间的操作（比较和随机数生成）。因此，pick 方法的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

综合以上两点，这个类的两个主要操作的时间复杂度如下：

构造函数：O(1)
pick 方法：O(n)

2. 空间复杂度

构造函数 Solution(int[] nums)：在构造函数中，我们只是存储了输入数组 nums 的引用和一个 Random 对象。由于没有使用额外的数据结构来存储数组 nums 的副本或与数组大小成比例的其他信息，所以构造函数的空间复杂度是 O(1)。
pick(int target) 方法：在 pick 方法中，我们使用了两个额外的变量 count 和 res，它们都是整数类型，因此它们的空间占用是常数。这个方法没有使用额外的数据结构，所以它的空间复杂度也是 O(1)。

综合以上两点，这个类的空间复杂度是：

构造函数：O(1)
pick 方法：O(1)

因此，整个 Solution 类的空间复杂度是 O(1)。

五、总结知识点

类定义：代码定义了一个名为 Solution 的类，这是面向对象编程的基本概念。
成员变量：Solution 类中有两个成员变量 nums 和 random，分别用于存储输入的整数数组和一个随机数生成器。
构造函数：Solution 类包含一个构造函数 Solution(int[] nums)，用于初始化成员变量。
方法定义：pick(int target) 是一个类方法，用于根据目标值 target 随机选择一个索引。
数组的遍历：在 pick 方法中，通过一个 for 循环遍历数组 nums。
条件判断：在 for 循环中，使用 if 语句检查当前元素是否等于目标值 target。
计数器：变量 count 用来记录目标值 target 出现的次数。
随机数生成：使用 Random 类的 nextInt(int bound) 方法生成一个随机数，这个方法生成一个介于 0（包含）和指定值 bound（不包含）之间的随机整数。
概率选择：通过 if (random.nextInt(count) == 0) 语句，实现了一个概率选择机制，确保每个等于 target 的索引都有相同的概率被选中。
返回值：pick 方法返回一个整数，即随机选择的索引。