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