侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 189 篇文章
  • 累计创建 46 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

Random sampling in Big Data -- Reservoir Sampling

996worker
2022-04-25 / 0 评论 / 0 点赞 / 100 阅读 / 516 字
温馨提示:
本文最后更新于 2022-04-29,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

需求

给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。

该数组很大, 可能存在海量下标.

解决方案

1. HashMap存储各种下标信息

不可以, 因为下标很多, 导致HashMap过大

  • 时间复杂度:初始化消耗O(n),给出索引为O(1),其中nnums的长度。

  • 空间复杂度:O(n)。我们需要 O(n) 的空间存储 n 个下标。

2. 蓄水池算法

image.png

代码

class Solution {
    int[] nums;
    Random random;

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

    public int pick(int target) {
        int ans = 0;
        int count = 0;

        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == target) {
                count++; // 第 cnt 次遇到 target
                if (random.nextInt(count) == 0) {
                    ans = i;
                }
            }
        }
        return ans;
    }
}

  • 时间复杂度:初始化为O(1),pick 为 O(n),其中 nnums 的长度。

  • 空间复杂度:O(1)。只需要常数的空间保存若干变量。

总结

典型地用时间换空间的应用.

0

评论区