专栏首页眯眯眼猫头鹰的小树杈leetcode398. Random Pick Index

leetcode398. Random Pick Index

题目要求

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;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode442. Find All Duplicates in an Array

    存在一个整数数组,其中的所有元素都位于1~n之间,其中n是数组的长度。有的元素出现了一次,而有的元素出现了两次。找到数组中所有出现两次的数字。

    眯眯眼的猫头鹰
  • leetcode473. Matchsticks to Square

    Remember the story of Little Match Girl? By now, you know exactly what matchstic...

    眯眯眼的猫头鹰
  • leetcode448. Find All Numbers Disappeared in an Array

    假设一个长度为n的整数数组,数组中的元素的值位于[1,n]区间中。问,该数组中有哪些[1,n]区间中的整数没有出现?

    眯眯眼的猫头鹰
  • Leetcode 26. Remove Duplicates from Sorted Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Remove Duplicates from Sorted Array II

    Tyan
  • Move Zeroes

    Tyan
  • 【LeetCode】旋转数组

    韩旭051
  • Leetcode 747. Largest Number At Least Twice of Others

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • leecode刷题(8)-- 两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    希希里之海
  • leetcode442. Find All Duplicates in an Array

    存在一个整数数组,其中的所有元素都位于1~n之间,其中n是数组的长度。有的元素出现了一次,而有的元素出现了两次。找到数组中所有出现两次的数字。

    眯眯眼的猫头鹰

扫码关注云+社区

领取腾讯云代金券