随机数索引

难度:

标签:

题目描述

给你一个可能含有 重复元素 的整数数组 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⁴
-2³¹ <= nums[i] <= 2³¹ - 1
target 是 nums 中的一个整数
最多调用 pick 函数 10⁴ 次

代码结果

运行时间: 76 ms, 内存: 20.4 MB

/*
 * 思路：
 * 1. 使用 Java Stream 初始化时保存输入的数组 nums。
 * 2. pick 方法使用 Stream 找出所有等于 target 的索引。
 * 3. 使用随机数选择一个索引返回。
 */
 
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
class Solution {
    private int[] nums;
    private Random random;
 
    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }
 
    public int pick(int target) {
        List<Integer> indices = IntStream.range(0, nums.length)
                .filter(i -> nums[i] == target)
                .boxed()
                .collect(Collectors.toList());
        return indices.get(random.nextInt(indices.size()));
    }
}

解释

方法:

该题解采用了哈希表的思路。在初始化时，遍历整个数组，将每个数字出现的索引存储在对应的哈希表中，key为数字，value为该数字出现的所有索引列表。在pick方法中，如果目标数字已经在哈希表中，则直接从对应的索引列表中随机选择一个索引返回；否则，遍历数组，找到目标数字的所有索引，存入哈希表中，然后从索引列表中随机选择一个索引返回。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在初始化过程中没有直接建立完整的哈希表，而是选择在首次调用pick方法时才为特定目标数字填充索引？

▷

这种做法是基于空间和性能权衡的考虑。在初始化过程中如果直接建立完整的哈希表，那么将需要一次性处理数组中的所有元素，这不仅会增加初始化的时间，还可能导致大量不必要的内存消耗，特别是当数组中的元素种类非常多时。通过延迟加载（即在首次需要时才处理特定数字），可以减少不必要的计算和内存使用，尤其是在实际使用中如果只有少部分数字被频繁查询的场景。

🦆

在pick方法中，如果目标数字的索引已经在哈希表中，直接进行随机选择的过程是否会引入任何概率偏差？

▷

不会引入概率偏差。因为每个索引在哈希表中只被记录一次，且每次随机选择是基于同一列表进行的，这保证了每个索引被选中的概率是均等的，满足均匀随机性要求。只要随机选择函数本身不具偏差，这种方法不会引入额外的概率偏差。

🦆

对于极大数组或高频率调用pick方法的场景，这种实现的性能表现如何？

▷

对于极大的数组，这种实现在首次查询任何数字时可能会有较高的延迟，因为需要遍历整个数组以构建哈希表中特定数字的索引列表。然而，一旦索引列表被创建，后续的查询将非常快速。在高频率调用pick方法的场景下，如果大部分数字的索引已经被缓存，则性能会非常好。但如果频繁查询未缓存的数字，则可能导致性能下降，因为每次都需要进行数组遍历。

🦆

在多次调用pick方法时，这种实现是否能保持目标数字索引选择的均匀随机性？

▷

可以保持均匀随机性。每次pick方法被调用时，都是从存储的索引列表中随机选择一个索引，这些索引列表在创建时就已经包含了目标数字的所有出现位置，且以后不会更改。这确保了每个索引被选中的概率是相等的。只要使用的随机选择方法是公正的，多次调用pick方法都能维持均匀随机性。

相关问题

链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 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中的一个，每个元素被返回的概率相等。

提示：

链表中的节点数在范围 [1, 10⁴] 内
-10⁴ <= Node.val <= 10⁴
至多调用 getRandom 方法 10⁴ 次

进阶：

如果链表非常大且长度未知，该怎么处理？
你能否在不使用额外空间的情况下解决此问题？

黑名单中的随机数

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言内置随机函数的次数。

实现 Solution 类:

Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

示例 1：

输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

提示:

1 <= n <= 10⁹
0 <= blacklist.length <= min(10⁵, n - 1)
0 <= blacklist[i] < n
blacklist 中所有值都不同
pick 最多被调用 2 * 10⁴ 次

按权重随机选择

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的概率为 w[i] / sum(w) 。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

示例 1：

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

提示：

1 <= w.length <= 10⁴
1 <= w[i] <= 10⁵
pickIndex 将被调用不超过 10⁴ 次

整数替换除法求值