Reservoir Sampling (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（398:Medium）（非常经典题）Random Pick Index

• randomly select an int from 0 to the nums of target. If x equals 0, set the res as the current index. The probability is always 1/nums for the latest appeared number. For example, 1 for 1st num, 1/2 for 2nd num, 1/3 for 3nd num (1/2 * 2/3 for each of the first 2 nums). int x = rand.nextInt(++total);

    int[] nums;
    Random rand;
    public _398_RandomPickIndex(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }
    public int pick(int target) {
        int total = 0;
        int res = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                // randomly select an int from 0 to the nums of target. If x equals 0, set the res as the current index. The probability is always 1/nums for the latest appeared number. For example, 1 for 1st num, 1/2 for 2nd num, 1/3 for 3nd num (1/2 * 2/3 for each of the first 2 nums).
                int x = rand.nextInt(++total); 
                res = x == 0 ? i : res;
            }
        }
        return res;
    }

2.（384:Medium）（经典题）Shuffle an Array

• 思路：每次往后读取数组的时候，当读到第i个的时候以1/i的概率随机替换1～i中的任何一个数，这样保证最后每个数字出现在每个位置上的概率都是相等的。即，总是从前j个数中选取一个数字i，放置到当前位置上。

3.（382:Medium）（非常经典题）Linked List Random Node

• 也是应用reservoir sampling思想进行求解，代码如下:

    ListNode head;
    Random random;
    
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode h) {
        head = h;       
        random = new Random();        
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        
        ListNode c = head;
        int r = c.val;
        for(int i=1;c.next != null;i++){
            
            c = c.next;
            //if(random.nextInt(i + 1) == i) r = c.val; //随机数等于i也行
            if(random.nextInt(i + 1) == 0) r = c.val;   
        }
        
        return r;
    }