T4-随机问题.md

随机问题

随机问题是一个考察点相对而言比较碎的问题，在leetcode或面试中相对并不是特别高频。 但该题目技巧性较强，相对来说容易掌握记忆，为了避免在面试中遇到该类题目时痛苦求索，本章节对随机问题做一个简单的梳理，对面试刷题还是大有裨益的。

随机问题可以包括： 采样和生成两大类

• 随机选取算法 (shuffle): 掌握洗牌算法
• 概率随机生成问题 (rand())
• 根据概率选取问题 (weight sampling)

384. 数组打乱shuffle

设计算法来打乱一个没有重复元素的数组。

• 洗牌算法： 如何保证概率随机性： 保证采样空间完整n!
• 两种思路：
  • 暴力算法：每次从数组中随机选择一个数字处理，重复N次构成新数组，并移除原数组的相应元素(即保证无放回随机采样，采样空间为n!)
  • 时间复杂度：O(N^2)
• Fisher-Yates 洗牌算法：每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数 rand() % (n - i) + i
  • 时间复杂度: O(N) 使用rand()%()来生成索引，不需要额外的空间；
  • 理论上同样是n!的采样空间
• 关键点 ： 洗牌算法

class Solution {
public:
    vector<int> data;
    Solution(vector<int>& nums) {
        data = nums;
    }
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return data;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        vector<int> nums(data);
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int t = rand() % (n - i) + i ;
            swap(nums[i], nums[t]);
        }
        return nums;
    }
};

470. 用Rand7实现Rand10 *

• 如果是要用rand10 实现 rand7 直接取1～7之间的值即可，这种情况下取到的值也是等概率分布的
• 对于 (randX()-1)*Y + randY() 可以得到[1, X*Y]之间的等概率分布
• 本题也是利用这个基本理论，得到[1,49]之间的等概率分布，然后拒绝其中大于40的部分，剩下部分来得到rand10()
  • **可以对拒绝空间进行进一步优化，对于被拒绝的部分即rand9(), 可以得到 [1,63] **的概率分布空间
  • 继续对拒绝空间部分1~3进行利用 rand3(), 可以得到[1,21] 拒绝空间只有1，这样的采样效率会大幅提升
• 关键点： (randX()-1)*Y + randY()

class Solution {
public:
    int rand10() {
        while(true) {
            // (randx() - 1)*Y + randY()
            int a = (rand7() - 1)*7 + rand7();
            if (a <= 40)
                return (a )%10 + 1;
            a = (a - 40 - 1)* 7 + rand7();
            if (a <= 60) 
                return (a )%10 + 1;
            a= (a - 60 - 1)* 7 + rand7();
            if (a <= 20) 
                return (a )% 10 + 1;
        }
        return 0;
    }
};

528. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比

• 计算前缀和数组， 在[0,sum-1]生成随机数，然后在前缀和数组中搜索首个大于随机数的前缀和，即对应的下标 （二分搜索找上届： upper_bound）
• 时间复杂度： O(logN)
• 关键点： 前缀和 + 二分查找

class Solution {
public:
    vector<int> prob;
    int probSum = 0;
    Solution(vector<int>& w) {
        int pred = 0;
        for (int i = 0; i < w.size(); i++) {
            prob.push_back(pred + w[i]);
            pred = prob.back();
        }
        probSum = prob.back();
    }
    
    int pickIndex() {
        int idx = rand() % probSum ; // 设置
        int left = 0;
        int right = prob.size() - 1;
        int ans = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prob[mid] <= idx) { // upper_bound的关键
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        // for (int i = 0; i < prob.size(); i++) {
        //     if (idx <= prob[i]) {
        //         return i;
        //     }
        // }
        return left;
    }
};

其中upper_bound的搜索过程也可以写成下面的这种格式

int pickIndex() {
    int idx = rand() % probSum;
    int left = 0;
    int right = prob.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (prob[mid] <= idx) {
            left = mid + 1;
        } 
        else {
            right = mid - 1;
        }
    }
    return left;
}