算法: 随机选择相同数字的索引398. Random Pick Index-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法: 随机选择相同数字的索引398. Random Pick Index。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

398. Random Pick Index

Given an integer array nums 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.
Implement the Solution class:

Solution(int[] nums) Initializes the object with the array nums.
int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i’s, then each index should have an equal probability of returning.

Example 1:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

Constraints:

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
target is an integer from nums.
At most 104 calls will be made to pick.

用defaultdict建立值对应的索引列表

from collections import defaultdict  # 导入 defaultdict 类，用于创建默认字典
from typing import List  # 导入 List 类型注释
import random  # 导入 random 模块，用于生成随机数

class Solution:

    def __init__(self, nums: List[int]):
        self.rand = random.Random()  # 创建一个 random.Random 对象，用于生成随机数
        self.indices = defaultdict(list)  # 创建一个默认字典，其默认值类型为 list
        
        # 遍历 nums 列表，并将每个元素的索引存储在字典中
        for i, num in enumerate(nums):
            self.indices[num].append(i)
        
    def pick(self, target: int) -> int:
        l = len(self.indices[target])  # 获取目标元素在 nums 中出现的次数（即索引列表的长度）
        
        # 随机选择一个索引并返回
        random_index = self.indices[target][self.rand.randint(0, l - 1)]
        return random_index

# 示例用法：
# obj = Solution(nums)
# param_1 = obj.pick(target)

复杂度分析：

时间复杂度:
init 方法：O(N)，其中 N 是 nums 列表的长度。
pick 方法：O(1)，因为我们只是从一个已知长度的列表中随机选择一个元素。
空间复杂度:
O(N)，其中 N 是 nums 列表的长度。这是因为在最坏的情况下，nums 中的每个数字都是唯一的，因此我们需要为每个数字存储一个索引。

解释defaultdict

defaultdict 是 Python 标准库 collections 中的一个类，它继承自内置的 dict 类。与普通的字典不同，defaultdict 允许你为字典中不存在的键提供一个默认值。这样，当你尝试访问一个不存在的键时，defaultdict 会自动为该键创建一个条目，并将其设置为你提供的默认值。

这个特性在很多情况下都非常有用，尤其是当你需要收集数据到列表或其他集合类型的时候。

使用示例：

from collections import defaultdict

# 使用 list 作为默认值类型
d = defaultdict(list)

# 现在，当你访问一个不存在的键时，defaultdict 会自动创建一个空列表作为该键的值
print(d["a"])  # 输出 []

# 你可以像普通字典一样添加键值对
d["a"].append(1)
d["a"].append(2)
d["b"].append(3)

print(d)  # 输出 defaultdict(<class 'list'>, {'a': [1, 2], 'b': [3]})