# 随机算法 & 数据结构

* **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)](https://leetcode.com/problems/insert-delete-getrandom-o1/)

实现 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 用。**

```java
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](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/)

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

```java
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).](http://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/)

这个也是平均复杂度，所用的技巧和上一题完全一样，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 就是目标元素。**

```java
    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)](https://www.quora.com/What-is-an-intuitive-explanation-of-reservoir-sampling)

### 题目描述： 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) 空间。算法和测试代码如下：

```java
    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](https://leetcode.com/problems/linked-list-random-node/)

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

```java
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](https://leetcode.com/problems/shuffle-an-array/)

[Shuffle array, Fisher–Yates shuffle, Knuth 洗牌算法](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)

### 代码和流程惊人的简单：

* **遍历每个 i ，随机从 i 还有 i 后面的区间抽一个数，和 i 交换；**
* **重点是 index = 【i, n - 1】区间。每个元素有留在原位置的概率。**

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/sui_ji_suan_fa_and_shu_ju_jie_gou.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.