leetcode398. Random Pick Index

airborne007 发布于2019-08-16 15:07 / 2573人阅读

摘要：思路一的实现其实要是想在的时间内完成随机数的获取，只需要缓存每个数字出现的下标，但是这意味着需要先对数据进行遍历，并且还需要的空间来额外存储数字下标的集合。所以我们只能每次在获取数字的时候来统计数字出现的次数，然后针对次数获取随机数下标。

题目要求

Given an array of integers 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.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

设计一个数据结构，使得从该数据结构中查询一个数字时，能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。

思路一：O(2n)的实现

其实要是想在O(1)的时间内完成随机数的获取，只需要缓存每个数字出现的下标，但是这意味着需要先对数据进行遍历，并且还需要O(n)的空间来额外存储数字下标的集合。这违背了题目意思。所以我们只能每次在获取数字的时候来统计数字出现的次数，然后针对次数获取随机数下标。

代码如下：

    private int[] nums;
    private Random r;
    public Solution(int[] nums) {
        this.nums = nums;
        this.r = new Random();
    }
    
    public int pick(int target) {
        int count = 0;
        int result = -1;
        for(int i = 0 ; i
思路二：蓄水池问题
有没有可能在一次的遍历中，找到这个随机下标呢？这就涉及到一个概率问题，即当我在遍历过程中遇到这个数字时，我是否需要选择它作为我的结果值。
首先介绍一下蓄水池抽样算法。蓄水池抽样算法主要对应的是这样的一个问题，假设有一个非常大的数据集，或者是一个以流的形式作为输入的数据集，希望从中选择K个样本，此时我们可能无法把所有的样本都放在内存中，因此只能保存一个大小为K的集合，每次遇到一个数据时，决定是否将其放入样本中。
因此，假设当前遇到的数据总共有N个，如果N小于K，则每个数据被选中的概率为1，如果N>K，则每个数据被选中的概率为K/N，旧样本中数据被保留的概率为1 - K(N-K)/N即K/N，因此每一个旧的数据被替换掉的概率为1/N。
按照这个思路，我们在下面的遍历时，每遇到一个新元素，就判断当前选中的元素是否会被该元素替换掉即可。
    private int[] nums;
    private Random r;
    public Solution(int[] nums) {
        this.nums = nums;
        this.r = new Random();
    }
    
    public int pick(int target) {
        int count = 0;
        int result = -1;
        for(int i = 0 ; i

云服务器 GPU云服务器 pick Leetcod LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73289.html

[LeetCode] 398. Random Pick Index (Reservoir Sampl

Problem Given an array of integers 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. Note:The array siz...

edagarli 2019-08-16 13:46 评论0 收藏0
leetcode382. Linked List Random Node

摘要：题目要求要求从单链表中，随机返回一个节点的值，要求每个节点被选中的概率是相等的。假如一共有个物品，需要从其中挑选出个物品，要求确保个物品中每个物品都能够被等概率选中。对于这种等概率问题，简答的做法是通过随机数获取选中物品的下标。题目要求 Given a singly linked list, return a random nodes value from the linked li...

xiaodao 2019-08-16 17:58 评论0 收藏0
[LeetCode] 528. Random Pick with Weight

Problem Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight. Note: 1

wangjuntytl 2019-08-16 13:40 评论0 收藏0
Python学习之路30-接口：从协议到抽象基类

摘要：本篇内容将从鸭子类型的动态协议，逐渐过渡到使接口更明确能验证实现是否符合规定的抽象基类。抽象基类介绍完动态实现接口后，现在开始讨论抽象基类，它属于静态显示地实现接口。标准库中的抽象基类从开始，标准库提供了抽象基类。《流畅的Python》笔记。本篇是面向对象惯用方法的第四篇，主要讨论接口。本篇内容将从鸭子类型的动态协议，逐渐过渡到使接口更明确、能验证实现是否符合规定的抽象基类(Abst...

LucasTwilight 2019-07-30 16:57 评论0 收藏0
流畅的python读书笔记-第11章-接口：从协议到抽象基类

摘要：自己定义的抽象基类要继承。抽象基类可以包含具体方法。这里想表达的观点是我们可以偷懒，直接从抽象基类中继承不是那么理想的具体方法。抽象基类抽象基类的常见用途：实现接口时作为超类使用。然后，说明抽象基类如何检查具体子类是否符合接口定义，以及如何使用注册机制声明一个类实现了某个接口，而不进行子类化操作。如何让抽象基类自动识别任何符合接口的类——不进行子类化或注册。接口在动态类...

Kyxy 2019-07-30 16:38 评论0 收藏0