一、题目描述
给你一个可能含有 重复元素 的整数数组 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 - 1target是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方法返回一个整数，即随机选择的索引。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
