随机算法 & 数据结构

• rd.nextInt(n) 可以生成 [0 - n) 之间的整数，注意开区间。

• 一般要靠 arraylist，因为有 get() 函数。

• remove 任意位置是 O(n)，但是每次只 remove 末位的话，平均是 O(1)，在知道 index 的情况下 swap 一下就好了。

随机数的帖子

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=119376&highlight=%CB%E6%BB%FA

Insert Delete GetRandom O(1)

实现 O(1) 的 GetRaondom 可以通过如下方式：

• 生成范围随机数

• 对应的数据结构支持 O(1) get

• 可以维护连续 key 区间，保证随机数时间复杂度

于是一开始想了下自己维护一个 LinkedList，但是不支持 O(1) get 只能算了。。

ArrayList 的问题在于，它的任意位置 delete 操作是 O(n)，和自身长度成比例的，因为要 shift 元素，怎么能把这个操作变成 O(1) 呢？

这里要做个取巧的事，考虑到所有value都是 integer，我们可以直接 swap，这样删除 “尾巴” 就是 O(1) 的平均复杂度了。

• rd.nextInt(n) 可以生成 [0 - n) 之间的整数，注意开区间。

• 正好可以当 index 用。

import java.util.Random;

public class RandomizedSet {
    // Key : number
    // Value : corresponding index in arraylist
    Map<Integer, Integer> map;
    List<Integer> list;
    Random rd;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<Integer, Integer>();
        list = new ArrayList<Integer>();
        rd = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        // Set already has given value
        if(map.containsKey(val)) return false;

        map.put(val, list.size());
        list.add(val);

        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;

        int indexA = map.get(val);

        if(indexA != list.size() - 1) swap(list, map, indexA, list.size() - 1);

        map.remove(list.get(list.size() - 1));
        list.remove(list.size() - 1);

        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rd.nextInt(list.size()));
    }

    // a : list index of element a
    // b : list index of element b
    private void swap(List<Integer> list, Map<Integer, Integer> map, int a, int b){
        int valA = list.get(a);
        int valB = list.get(b);
        int indexA = map.get(valA);
        int indexB = map.get(valB);

        list.set(a, valB);
        list.set(b, valA);
        map.put(valA, indexB);
        map.put(valB, indexA);
    }
}

Insert Delete GetRandom O(1) - Duplicates allowed

• HashMap 的 value 只存一个 index 就不够用了，得存一个 Set<>，记录相同元素所有的 index，反正 add / remove 的平均复杂度都是 O(1)。

import java.util.*;

public class RandomizedCollection {
    Map<Integer, Set<Integer>> map;
    List<Integer> list;
    Random rand;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean flag = false;

        if(!map.containsKey(val)){
            flag = true;
            map.put(val, new HashSet<Integer>());
        }

        list.add(val);
        map.get(val).add(list.size() - 1);

        return flag;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        boolean flag = false;

        if(map.containsKey(val) && map.get(val).size() > 0){
            flag = true;
            int indexA = map.get(val).iterator().next();
            int indexB = list.size() - 1;
            swap(map, list, indexA, indexB);

            map.get(val).remove(list.size() - 1);
            list.remove(list.size() - 1);
        }

        return flag;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }

    // Swap elements at list index "a" and "b" in arraylist, and hashmap
    private void swap(Map<Integer, Set<Integer>> map, List<Integer> list, int indexA, int indexB){
        // O(1)
        int valA = list.get(indexA);
        int valB = list.get(indexB);

        // O(1) average 
        map.get(valA).remove(indexA);
        map.get(valB).remove(indexB);

        // O(1) average
        map.get(valA).add(indexB);
        map.get(valB).add(indexA);

        // O(1)
        list.set(indexA, valB);
        list.set(indexB, valA);

    }
}

(G) Implement HashTable with get,set,delete,getRandom functions in O(1).

这个也是平均复杂度，所用的技巧和上一题完全一样，ArrayList + HashMap

(G) Get random number except blacklist

http://www.1point3acres.com/bbs/thread-78548-1-1.html

设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输出的数字如果出现在其中就要剔除。（面试完之后，听人提醒这题很类似CTCI上的问题12.3） 这题面试官没让我写code，我说了几个答案他都觉得不满意，因为他想要一种“渐进的”方法解决此题

题目要求:

给定区间 [0，n]，和一个排好序的 blacklist，List<> 随机返回一个不在 blacklist 中的数。

分析：

这道题最简单的思路是先从 blacklist 的角度想。先生成一个[0, n] 之间的数，然后看这个数在不在 blacklist 里，如果在的话，再生成一次。

• 问题一：如果 blacklist 不是 set 的形式给的，至少要 binary search;

• 问题二：运气不好，或者 blacklist 非常大的话，我们可能要调用多次 getRandom，而这个 API 可能是非常贵的。

因此另一个思考角度是，从 white list 出发。

对于【0，10】，blacklist = 【1,2,3,7,8】来讲，white list = 【0,4,5,6,9,10】.因此假设我们有足够内存去维护 whitelist，我们可以直接生成并返回一个 white list 中的元素，这样可以保证一次 getRandom() 操作保证得到想要的元素。

假如 white list 内存放不下呢？

方法照旧。每次我们生成一个 white list 的合理 index 之后，我们要找的就是 “第 index + 1 个不在 blacklist 中的数”。这个可以通过扫 blacklist 实现，O(1) 的内存开销。

相当于实现了一个 index -> whitelist[index] 的 mapping，可以保证一次 getRandom() 就可以得到有效元素。

• i 从 0 到 n 循环，如果大于 blacklist 最后一个数，或者小于 blacklist 当前数，都 count --;

• 否则 blackPtr ++ ;

• 每次循环的时候，count 扣完了，当前 i 就是目标元素。

    static Random rand = new Random();

    public static int getRandom(int n, List<Integer> blackList){
        int totalNum = n + 1;
        int whiteListSize = totalNum - blackList.size();

        int index = rand.nextInt(whiteListSize);
        int count = index + 1;
        int blackPtr = 0;
        for(int i = 0; i <= n; i++){
            if(i > blackList.get(blackList.size() - 1) || i < blackList.get(blackPtr)){
                count --;
            } else {
                blackPtr ++;
            }

            if(count == 0) return i;
        }

        return -1;
    }

    public static void main(String[] args){
        List<Integer> blackList = new ArrayList<Integer>();
        blackList.add(1);blackList.add(2);blackList.add(3);
        blackList.add(7);blackList.add(8);
        blackList.add(13);blackList.add(19);blackList.add(20);
        for(int i = 0; i < 50; i++){
            System.out.print(" , " + getRandom(20, blackList));
        }
    }

huixuan : 我之前还想过这个问题可以变形成另外一个问题：比如产生长度为k的随机序列，序列中数字的值在[0, n]中sample，但是不可以有重复。要求讨论两个case: k和n差不多大、k远小于n

Random number generator with weight

题目描述：给定几种元素，以及对应的 weight，按每个元素的概率分布符合其 weight 的方式生成随机元素。

如：【0,1,2,3,4】 的 weights 【0.1, 0.2, 0.2, 0.4, 0,1】 ，按 weight 返回 【0,4】

核心是 cumulative distribution. 计算出 [0.1, 0.3, 0.5, 0.9, 1] 的 cdf 之后，我们可以随机返回一个 【0,1】 之间的数，然后对于 cdf array 做 binary search.

我们要寻找的，就是第一个 random number < cdf[i] 所对应的元素 num[i].

Reservoir Sampling (Quora)

题目描述： Given a data set of unknown size N, uniformly select k elements from the set such that each element has a 1/N probability of being chosen.

http://www.geeksforgeeks.org/reservoir-sampling/

分析 & 证明：

• 核心是 proof by induction.

• 从 k = 1 开始，对于第 i 个元素，我们有 1 / i 的几率让当前元素成为 candidate，相应的，有 (i - 1) / i 的概率直接扔掉这个新元素。

• 假设我们有 3 个元素，那么第 3 个元素只会被 check 一次，有 1/3 的几率留下，2/3 的几率被扔掉；

• 而它的前一个元素，2，会被 check 两次，一次是自己，一次是 3 的时候；而它成为最终选中的元素需要同时满足两个条件：

  • 考虑到自己的时候，随到了 keep : (1/i = 1/2 概率)

  • 考虑后面元素的时候，没替换掉它，即后面元素都 discard 了：(2/3 概率)

  • 两项相乘，等于 1/3.

• 这个 induction 的推导，对于任意有效 k 和 n 也都适用，从后往前。

  • 倒数第二个元素选中的概率 = (k / n - 1) * (n - 1 / n) = k / n

O(n) 时间，O(k) 空间。算法和测试代码如下：

    static Random rand = new Random();

    public static int[] reserviorSampling(int k, int[] nums){
        if(k >= nums.length) return nums;

        int i = 0;
        int[] rst = new int[k];
        for(; i < k; i++){
            rst[i] = nums[i];
        }

        for(; i < nums.length; i++){
            // random is exclusive
            int num = rand.nextInt(i + 1);
            if(num < k) rst[num] = nums[i];
        }

        return rst;
    }

    public static void main(String[] args){
        int[] count = new int[10];
        for(int i = 0; i < 10000; i++){
            int[] sampled = reserviorSampling(5, new int[]{0,1,2,3,4,5,6,7,8,9});
            for(int num : sampled) count[num]++;
        }

        for(int i = 0; i < 10; i++){
            System.out.println("Count of " + i + " " + count[i] + " times");
        }
    }

Linked List Random Node

刚写完这章的总结，leetcode 就搞了个蓄水池抽样的题出来。。好与时俱进啊！

import java.util.*;

public class Solution {
    ListNode head;
    ListNode rst;
    int count;
    Random rand;

    /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        rand = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode cur = head.next;
        rst = head;
        count = 2;
        while(cur != null){
            int num = rand.nextInt(count++);
            if(num == 0) rst = cur;
            cur = cur.next;
        }
        return rst.val;
    }
}

Shuffle an Array

Shuffle array, Fisher–Yates shuffle, Knuth 洗牌算法

代码和流程惊人的简单：

• 遍历每个 i ，随机从 i 还有 i 后面的区间抽一个数，和 i 交换；

• 重点是 index = 【i, n - 1】区间。每个元素有留在原位置的概率。

其原理非常类似于一群人在一个黑箱子里抽彩票，for 循环中的每次迭代相当于一个人，每次抽样范围 index = 箱子中剩下的所有彩票，其数量依次递减。到最后每个人虽然抽奖时箱子里彩票总数不同，但是获奖概率却是均等的。

import java.util.*;
public class Solution {
    int[] original;
    Random rand;
    public Solution(int[] nums) {
        original = nums;
        rand = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return original;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] rst = Arrays.copyOf(original, original.length);

        for(int i = 0; i < rst.length; i++){
            int index = rand.nextInt(rst.length - i) + i;

            int temp = rst[i];
            rst[i] = rst[index];
            rst[index] = temp;
        }

        return rst;
    }
}