leetcode398. Random Pick Index

栏目: 编程工具 · 发布时间: 6年前

内容简介:设计一个数据结构,使得从该数据结构中查询一个数字时,能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。其实要是想在O(1)的时间内完成随机数的获取,只需要缓存每个数字出现的下标,但是这意味着需要先对数据进行遍历,并且还需要O(n)的空间来额外存储数字下标的集合。这违背了题目意思。所以我们只能每次在获取数字的时候来统计数字出现的次数,然后针对次数获取随机数下标。代码如下:

题目要求

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<nums.length ; i++) {
            if(target == nums[i]) {
                count++;
            }
        }
        int index = r.nextInt(count);
        for(int i = 0 ; i<nums.length ; i++) {
            if(target == nums[i]) {
                index--;
                
                if(index == -1){
                    result = i;
                    break;
                }
            }
        }
        return result;
    }

思路二:蓄水池问题

有没有可能在一次的遍历中,找到这个随机下标呢?这就涉及到一个概率问题,即当我在遍历过程中遇到这个数字时,我是否需要选择它作为我的结果值。

首先介绍一下 蓄水池抽样算法 。蓄水池抽样算法主要对应的是这样的一个问题,假设有一个非常大的数据集,或者是一个以流的形式作为输入的数据集,希望从中选择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<nums.length ; i++) {
            if(nums[i] == target) {
                int index = r.nextInt(++count);
                if(index == 0) {
                    result = i; 
                }
            }
        }
        return result;
    }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

看见未来

看见未来

余晨 / 浙江大学出版社 / 2015-4-15 / 59.00元

【内容简介】 这是互联网群星闪耀的时代,巨人们用最尖端的技术和自成体系的哲学改变着我们的生活,甚至影响了整个世界和人类的历史进程。在这个时代,没有人可以避开互联网的渗透。互联网早已不是简单的技术变革,人们正试图赋予其精神和内涵,以期互联网能更好地为人类所用。 本书中作者 面对面地采访了包括马克·扎克伯格、埃隆·马斯克、杨致远、凯文·凯利、克里斯·安德森、罗伯特·希勒、迈克尔·莫瑞茨、凯......一起来看看 《看见未来》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具