08 随机数问题

384 打乱数组 (opens new window)

给定一个数组，要求实现两个指令函数。第一个函数 shuffle() 可以随机打乱这个数组，第二个函数 reset() 可以恢复原来的顺序。

输入是一个存有整数数字的数组，和一个包含指令函数名称的数组。输出是一个二维数组，表示每个指令生成的数组。

输入: ["Solution", "shuffle", "reset", "shuffle"] [[[1, 2, 3]], [], [], []]

输出: [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释: Solution solution = new Solution([1, 2, 3]); solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2] solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3] solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

解析：

​ 本题可以采用经典的 Fisher-Yates 洗牌算法，原理是通过随机交换位置来实现随机打乱，有正向和反向两种写法。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换，这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 ，否则生成最后的排列组合的概率就不对了。

​ 注意 reset 函数以及类的构造函数的实现细节，使用成员变量保存原数组。

class Solution {
private:
    vector<int> origin;

public:
    Solution(vector<int>& nums) {
        origin = nums;
    }
    
    vector<int> reset() {
        return origin;
    }
    
    vector<int> shuffle() {
        // 反向洗牌
        if(origin.empty()) return {};
        vector<int> shuffleNum(origin);
        for(int i=shuffleNum.size()-1;i>=0;--i){
            int pos = rand()%(i+1);
            swap(shuffleNum[i],shuffleNum[pos]);
        }
        // 正向洗牌
        /*
        int len = shuffleNum.size();
        for(int i=0;i<len;++i){
            int pos = rand()%(len-i);
            swap(shuffleNum[i],shuffleNum[i+pos]);
        }
        */
        return shuffleNum;
    }
};

528 按权重随机选择 (opens new window)

给定一个数组，数组每个位置的值表示该位置的权重，要求按照权重的概率去随机采样。

输入是一维正整数数组，表示权重；和一个包含指令字符串的一维数组，表示运行几次随机采样。输出是一维整数数组，表示随机采样的整数在数组中的位置。

输入: weights = [1,3], actions: ["pickIndex","pickIndex","pickIndex"]

输出: [0,1,1]

解释：在这个样例中，每次选择的位置都是不确定的，但选择第 0 个位置的期望为 1/4，选择第 1个位置的期望为 3/4。

解析：

​ 进一步读懂题目。假设有数组w: [1, 2, 3, 4], 那么这个数组的的和为 1 + 2 + 3 + 4 = 10。对应的得到 index {0,1,2,3} 的概率为 {1/10, 2/10, 3/10, 4/10}。现在要返回 {0,1,2,3} 中的随意一个index，但是要保证pickIndex()函数所得到这个index的概率是根据以上的权重来的。

​ 首先，求出前缀和表。paritial_sum()就是求前缀和，w[0] = W[0], w[1] = W[0] + W[1]...如此推算

​ 然后，求出前缀和表后最后一位数所包含的就是所有数字的和。用以上的例子 w.back() 最终会包含 1 + 2 + 3 + 4 = 10 ​ 接着，求出一个随机数，rand() % w.back(); 假设 w.back() = 10, 那么这里产生的数字是 0-9。如果我们继续用以上的例子的话那么其每个数字所对应取到的index便为，0 ：代表取到 index 0；1，2: 代表取到 index 1；3，4，5: 代表取到 index 2；6，7, 8, 9: 代表取到 index 3 ​ 最后，用以上的例子产生的前缀和表 [1, 3, 6, 10], 可以发现我们用得到的数字调用 upper_bound() 会刚好使其指向我们的 index 位置。0 的 upper_bound 会指向 index 0, 因为第一个比 0 大的数是 w[0] = 1；1, 2 的 upper_bound 会指向 index 1, 因为第一个比 1 或者 2 大的数是 w[1] = 3；3, 4, 5 的 upper_bound 会指向 index 2, 因为第一个比 {3, 4, 5} 大的数是 w[2] = 6；6, 7, 8, 9 的 upper_bound 会指向 index 3, 因为第一个比 {6，7, 8, 9} 大的数是 w[3] = 10;

class Solution {
private:
    vector<int> sums;
public:
    Solution(vector<int>& w) {
        sums = w;
        partial_sum(sums.begin(),sums.end(),sums.begin()); 
    }
    
    int pickIndex() {
        int pos = (rand()%sums.back()) + 1;
        return lower_bound(sums.begin(), sums.end(), pos) - sums.begin();
    }
};

382 链表随机节点 (opens new window)

给定一个单向链表，要求设计一个算法，可以随机取得其中的一个数字。

输入是一个单向链表，输出是一个数字，表示链表里其中一个节点的值。

// 初始化一个单链表 [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。 solution.getRandom();

解析：

​ 不同于数组，在未遍历完链表前，无法知道链表的总长度。这里可以使用水库采样：遍历一次链表，在遍历到第 m 个节点时，有 1/m 的概率选择这个节点覆盖掉之前的节点选择。采用水库算法满足每个点都有均等的概率被选择的随机性。

​ 水库采样，也称为蓄水池抽样算法。概算法常被用于大数据流中的随机抽样问题即：当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。该算法每次只保留一个数，当遇到第 i 个数时，以 1/i的概率保留它，(i-1)/i的概率保留原来的数，采用这种方式始终保持每个数被保留的概率是 1/N。例如，{1,2,3} 三个数以数据流的形式读取：1到达时将其以概率为 1/1 保留；2到达时以概率 1/2 保留，1 以 (2-1) / 2 即 1/2 * 1 = 1/2 保留；3 到达时以概率 1/3 保留，1 以 (3-1)/2 * 1/2 = 1/3 保留，同理 2 也以1/3保留。可以看出水库抽样算法可以始终保持每个数被保留的概率都是 1/N。

class Solution {
    ListNode* headNode;
public:
    Solution(ListNode* head) {
        headNode = head;
    }
    
    int getRandom() {
        int ans = headNode->val;
        ListNode* node = headNode->next;
        int i = 2;
        while(node){
            if(rand()%i == 0){
                ans = node->val;
            }
            ++i;
            node = node->next;
        }
        return ans;
    }
};

470 用 Rand7() 实现 Rand10() (opens new window)

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

解析：

​ 用现有范围随机数生成函数构造新的范围的随机数生成函数。这种问题分为两种情况：一种是缩小原有随机数生成函数的范围，另一种是扩展原有随机数生成函数的范围。

​ 第一种缩小范围情况较为简单，只需要将范围之外的随机数丢弃即可。

​ 第二种扩展范围的情况要用到一个公式，(randM()-1) * M + randM() 可以生成1～M*M范围内的等概率随机数。

class Solution {
public:
    int rand10() {
        int num = (rand7()-1)*7+rand7();
        while(num>10){
            num = (rand7()-1)*7+rand7();
        }
        return num;
    }
};