LeetCode398.随机数索引：「哈希表」&「水塘抽样」

浏览次数 : 次 2022-01-20

博文字数统计 : 766字 | 阅读所需时长 : 3分

× 文章目录

1. LeetCode398.随机数索引：「哈希表」&「水塘抽样」

LeetCode398：随机数索引
- 时间：2022-01-20
- 力扣难度：Medium
- 个人难度：Medium-
- 数据结构：数组
- 算法：水塘抽样、概率论与数理统计

LeetCode398.随机数索引：「哈希表」&「水塘抽样」

1. 题目描述

题目：原题链接
- 给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。
- 您可以假设给定的数字一定存在于数组中。
- 注意：数组大小可能非常大。使用太多额外空间的解决方案将不会通过测试。
输入输出规范：设计题无需考虑输入输出

2. 方法一：哈希表

思路：哈希表存数值的索引列表
- 首先在构造方法中遍历数组，存入哈希表中，key为数值，value为对应的索引的List
- 返回索引时，先从Map中找到该数值对应的List索引，再通过随机数等概率返回一个索引

题解：哈希表+一次遍历

class Solution {
    // 方法一：哈希表
    private int n;
    Random random;
    private Map<Integer, List<Integer>> map = new HashMap<>();

    public Solution(int[] nums) {
        this.n = nums.length;
        random = new Random();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i]).add(i);
                continue;
            }
            List<Integer> list = new ArrayList<>();
            list.add(i);
            map.put(nums[i], list);
        }
    }

    public int pick1(int target) {
        List<Integer> targetList = map.get(target);
        int size = targetList.size();
        int index = random.nextInt(size);
        return targetList.get(index);
    }
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

3. 方法二：水塘抽样

思路：概率论：随机抽样
- 实际上，本题属于数据流中获取随机元素的问题，在数学上有一种专门用于解决该类问题的算法：水塘抽样算法，也称为蓄水池抽样算法
- 该算法的主要思想是
  - 维护一个初始值为0的变量 i，表示当前遍历到的元素的序号，遍历整个数据流(链表)，在遍历的过程中每次对维护的序号变量进行++操作
  - 然后生成一个[0, i)的随机数，当这个随机数等于0的时候，就选择当前遍历到的元素作为结果返回
  - 这样以来，我们就不需要知道整个元素的集合的大小，也不需要额外的空间去存放元素，非常适合在大数据场景下不知道数据具体个数时，随机返回指定个数(可以不为1)元素
- 该算法的证明和扩展到随机返回N个数据详见：No1-LC382-链表随机节点

题解

class Solution{
    private int n;
    int[] nums;
    Random random;

    public Solution(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        random = new Random();
    }

    public int pick(int target) {
        int index = -1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                count++;
                if (random.nextInt(count) == 0) index = i;
            }
        }
        return index;
    }
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-20 00:22:33
最后更新： 2022-01-27 20:44:38
本文标题： LeetCode398.随机数索引：「哈希表」&「水塘抽样」
本文链接： https://chthollists.github.io/post/46397f85.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！