带权重的随机选择算法 :: labuladong的算法小抄

[labuladong]

文章链接点这里：带权重的随机选择算法

评论礼仪 见这里，违者直接拉黑。

[zyxing-Andrew]

今天面Cisco就出了这道.... 细节啊，卡了我半天，总结就是一定要私下自己手写

[z-ak-z]

java方法，前缀数组下标从0开始，最终的结果不需要再-1了：

class Solution {
        private Random random = new Random();
        private int[] preSum;
        private int n;
        public Solution(int[] w) {
            this.n = w.length;
            // 前缀数组，下标0就是原数组w[0]
            preSum = new int[n];
            // 下标0就是原数组w[0]
            preSum[0] = w[0];
            for (int i = 1; i < n; i++) {
                preSum[i] = preSum[i-1] + w[i];
            }
        }

        public int pickIndex() {
            // 保证取到[1, preSum[n-1]]的闭区间
            int target = random.nextInt(preSum[n-1]) + 1;
            // right可以从n-1开始，也可以从n开始，对结果的正确性没有影响
            int left = 0, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                // 如果找到了，直接去当前的下标
                if (preSum[mid] == target) {
                    left =mid;
                    break;
                } else if (preSum[mid] > target) {
                    // 向左找，因为当前mid的值大于target，可能是"第一个大于target"的值，所以不能丢弃mid
                    // 如果mid的值不再需要了(最终不会取到现在的mid)，那么就可以right=mid-1；
                    right = mid;
                } else {
                    // 向右找，因为当前的mid的值比target小，永远不会取到了。所以left=mid+1;
                    left = mid + 1;
                }
            }
            // left代表的含义：
            // 当目标元素 target 不存在数组 nums 中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读：
            // 1、返回的这个值是 nums 中大于等于 target 的最小元素索引。
            // 2、返回的这个值是 target 应该插入在 nums 中的索引位置。
            // 3、返回的这个值是 nums 中小于 target 的元素个数。
            return left;
        }
    }

[bruceeewong]

这里直接跳，在这一题没问题（因为权重没有0的情况，所以找到的前缀和，其下标-1就是答案

if (preSum[mid] == target) {
  left =mid;
  break;
}

但如果存在权重为0的情况会出问题。因为会出现前缀和 前后相等，那就要取左边界的下标咯

[PeachLuis]

不懂就问，为啥后面的这些，二分的写法都不用总结的，还是用这种大多数人用的呢

[tsangz2013]

等价于 random from [0...sum(w)-1]，然后找这个值的右插入位置：

target = random.randint(0, preSum[n-1]-1) # from 0 to sum(w)-1, inclusive
return bisect_right(preSum, target) - 1 # find the right most position to insert this target
"""
preSum = 0,1,4,6,7,
target = 0: return 1-1 = 0
target = 1 or 2 or 3: return 2-1 = 1
target = 4 or 5: return 3-1 = 2
...
"""

[exotrl]

为什么前缀和数组中 0 本质上是个占位符啊？这句话还是不太理解，就是为什么target的范围不是【0，7】？

[bugcat9]

呜呜，我理解的是因为随机的是整数，也就是离散的导致这样子。比如：【0，7】有0,1,2,3,4,5,6,7。分母多了一个【1,7】有1，2，3，4，5，6，7,概率分布为{1}，{2，3，4}，{5，6}，{7}是符合的。

[susc]

既然不能取0，那为什么不是(0, 7]呢？反正是找大于等于它的整数，只会取到1, 2, 3, 4, 5, 6, 7

[susc]

我明白了，博主的java算法取的是整数，不会出现小数。

[labuladong]

@thy485280869 不看就滚，别搁这叽叽歪歪

[labuladong]

@exotrl 你可以看下 前缀和数组技巧 里面如何构建 preSum 数组的

[WanrenDing]

是不是不一定要用搜索左侧边界的二分法呀，我用了最普通的二分搜索也通过了，把返回值改成left就可以了（虽然和模板不一样，但是感觉这样好像更容易理解

[labuladong]

@WanrenDing 如果你能说清楚为什么这样写能过，那就算是真的理解了

[zherui-lin]

@WanrenDing 因为这道题每个位置必定占有一定权重w[i]不可能为0，所以preSum里不会有重复元素，那么二分找到的第一个位置必然就是左侧边界了；返回值left能保证是target应插入preSum的位置的原因是我们取的是左闭右开的区间，left会移动至mid的右边一位，所以能保证left最终落在恰好比target大的位置（当然你return right也行）

[siren-xiaohu]

@labuladong 请问使用左右都闭合的区间怎么写，我用了你的左右都闭合的区间的二分方法没有成功。求大佬教教

[a1442792195]

class Solution {
    private int[] preSum ;
    private Random rand = new Random() ;
    public Solution(int[] w) {
        preSum = new int[w.length+1] ;
        preSum[0] = 0 ;
        for(int i=1;i<preSum.length;i++){
            preSum[i] = preSum[i-1] + w[i-1] ;
        }
    }
    public int pickIndex() {
        int n = rand.nextInt(preSum[preSum.length-1]) + 1 ;
        return left_bound(preSum,n) - 1 ;

    }
    private int left_bound(int[] nums, int target){
        int left = 0 , right = nums.length-1 ;
        while(left<=right){
            int mid = left + (right - left) / 2 ;
            if(target<nums[mid]){
                right = mid - 1 ;
            }else if(target>nums[mid]){
                left = mid + 1 ;
            }else if(target == nums[mid]){
                right = mid - 1 ;
            }
        }
        return left ;
    }
}

[LeeX852]

class Solution {
    private int[] preSum;
    private Random rand = new Random();

    public Solution(int[] w) {
        int n = w.length;
        // 构建前缀和数组
        preSum = new int[n + 1];
        preSum[0] = 0;
        // 计算前缀和
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + w[i - 1];
        }
    }
    
    public int pickIndex() {
        int n = preSum.length;
        // 随机选择一个数字，应该在区间[1, preSum[n - 1]]
        int target = rand.nextInt(preSum[n - 1]) + 1;
        // 别忘了前缀数组和原始数组有一位偏移
        return left_bound(preSum, target) - 1;
    }

    private int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid - 1;
            }
        }
        // if (left > nums.length || nums[left] != target) {
        //     return -1;
        // }
        return left;
    }
}

[oocococo]

这题还可以用lottery算法，空间复杂度O（1）就可以做出来

[lycheejuicyy]

[a1442792195]

class Solution {
    private int[] preSum ;
    private Random rand = new Random() ;
    public Solution(int[] w) {
        preSum = new int[w.length+1] ;
        preSum[0] = 0 ;
        for(int i=1;i<preSum.length;i++){
            preSum[i] = preSum[i-1] + w[i-1] ;
        }
    }
    public int pickIndex() {
        int n = rand.nextInt(preSum[preSum.length-1]) + 1 ;
        return left_bound(preSum,n) - 1 ;

    }
    private int left_bound(int[] nums, int target){
        int left = 0 , right = nums.length-1 ;
        while(left<=right){
            int mid = left + (right - left) / 2 ;
            if(target<nums[mid]){
                right = mid - 1 ;
            }else if(target>nums[mid]){
                left = mid + 1 ;
            }else if(target == nums[mid]){
                right = mid - 1 ;
            }
        }
        return left ;
    }
}

[billgoo]

请问有朋友用 Python 写的吗
我发现一个问题，就是在随机生成数字的时候，用以下这个是正确的

num = random.uniform(0, self.pre_sum[-1]) + 1

但是用 randint 在 leetcode 上跑就会报错

num = random.randint(0, self.pre_sum[-1]) + 1

[libxing]

同样左右闭合的左侧边界二分搜索过不了，return是return left==0 ? 0 : left-1; 我太菜了www

[yonggui-yan]

打卡

二分搜索的妙用！

[Maxiah]

带权重：搜索左侧边界target = random[1, preSum[n-1]]

w = [1,3,2,1] preSum = [0, 1, 4, 6, 7]

target 的取值范围[1, 7]
比如搜索2，返回的是preSum[2] = 4；搜索3，返回的是preSum[2] = 4，搜索4，返回的是preSum[2] = 4
这样是不是就是占3/7的概率

[guqihao-7]

我倒是挺喜欢lol还有lol手游的匹配机制的，因为在这两款游戏中，我都是那条菜狗😋

[codezcq]

class Solution {

    int [] presum = null;
    Random random = new Random();
    
    public Solution(int[] w) {
        int n = w.length;
        if(n==0)return;
        presum = new int[n];
        presum[0] = w[0];
        for(int i = 1 ; i<n;i++){
            presum[i] = presum[i-1]+w[i];
        }
    }
    
    public int pickIndex() {
        int n = presum.length;
        int target = random.nextInt(presum[n-1])+1;
        return left_bound(target);
    }
    public int left_bound(int target){
        int left = 0 , right = presum.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(presum[mid]>target){
                right = mid - 1;
            }else if(presum[mid]<target){
                left = mid + 1;
            }else if(presum[mid] == target){
                left = mid + 1;
            }
        }
        if(right<0)return left;
        return presum[right] == target? right: left;

    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */

这里我发现了一个小细节 首先前缀和可以不使用n+1 只用n 东哥可能是为了和前面讲的前缀和呼应
其次 在二分搜索这里
当无法找到target的时候 也就是说其实 presum[mid] == target 这个条件是报废的 那么不管是向左搜索还是向右搜索
其实都是一样的 最终的结果是left的索引 代表大于等于target的最小索引
当可以找到target的时候 如果才有向左搜索 那么最终left的值还是会落在代表大于等于target的最小索引上 但这并不代表向右搜索不能返回结果 向右搜索最终是以 left = mid + 1也就是left多了一位 此时right落在了target上

所以我这里写的代码的意思是 如果target能被找到 那么就返回right 找不到 那就乖乖返回left
东哥的思想更加简单 我这里只是对为什么使用左搜索而不是右搜索做补充

[labuladong]

👍

[fantian007]

class Solution {
    // 前缀和数组
    private preSum: number[] | undefined;

    constructor(w: number[]) {
        const n = w.length;
        this.preSum = new Array(n + 1);
        this.preSum[0] = 0;

        for (let i = 1; i <= n; i++) {
            this.preSum[i] = this.preSum[i - 1] + w[i - 1];
        }
    }

    pickIndex(): number {
        const last = this.preSum.slice(-1)?.[0];

        const random = Math.ceil(Math.random() * last);

        const i = this.preSum.findIndex(f => f >= random);

        return i - 1;
    }
}

[fantian007]

偷懒了

[bugcat9]

东哥写的还是那么巧妙，感觉细节还是多的，比如随机从[1,7]

[SUN7700]

不太理解这一部分，还有那右侧边界返回值的意义是什么，希望东哥可以整理到前文【我写了首诗，，，，】

[KScaesar]

我下方回文
有提供一些 二分搜尋找 大於 小於 的資料

[NayelyA]

type Solution struct {
    presum []int
}


func Constructor(w []int) Solution {
    n:=len(w)
    presum:=make([]int,n+1)
    presum[0]=0
    for i:=1;i<=n;i++{
        presum[i] = presum[i-1] + w[i-1]
    }
    return Solution{presum}
}


func (this *Solution) PickIndex() int {
    n:=len(this.presum)
    target:=rand.Intn(this.presum[n-1])+1
    return leftBound(this.presum,target) - 1
}

func leftBound(nums []int,target int) int{
    if len(nums) == 0 {
        return -1
    }
    left,right:=0,len(nums)
    for left<right {
        mid:=left + (right-left)>>2
        if nums[mid] == target {
            right = mid
        }else if nums[mid] < target{
            left = mid + 1
        }else if nums[mid] > target{
            right = mid
        }
    }
    return left
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */

[KScaesar]

如何快速寻找数组中大于等于目标值的最小元素？

提供用 二分搜尋找 gt ge lt le 的相關資料
該用 left_boud 還是 right_boud

其實有一定的規律
可以背下來
注意 找 lt or le
index 需要 減 1

def find_lt(a, x): 解讀為
在 a 找出 小於 x 的 索引

https://docs.python.org/3/library/bisect.html#searching-sorted-lists
https://github.com/python/cpython/blob/main/Lib/bisect.py#L19

[Nighty-night]

生成随机数，int target = rand.nextInt(preSum[n - 1]) + 1;
为啥要+1？这个不太懂

[yusun97]

生成随机数的方程定义如下
public int nextInt(int bound)
Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive)
生成范围是 [0, preSum[n-1]) 左闭右开
而我们需要的是 [1, preSum[n-1]] 左闭右闭
所以需要+1

[weixueman]

前缀数组不用占位符也能做，即preSum[0] = w[0]，而且这样感觉更好理解，不需要返回结果减1。不过这样二分搜索时要需要使用双闭区间，左闭右开会有问题，同时随机数的范围也要双闭

[bruceeewong]

20230110 打卡

[ChanganYang]

为啥用闭区间二分搜索做这个就通不过呢😰

[ChanganYang]

不好意思是我自己有个小地方写错了😂

[CarlLy7]

打卡

[Tyler03118]

没懂为什么不能用右边界