fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
带权重的随机选择算法 :: labuladong的算法小抄
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;
}
}
等价于 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
...
"""
是不是不一定要用搜索左侧边界的二分法呀，我用了最普通的二分搜索也通过了，把返回值改成left就可以了（虽然和模板不一样，但是感觉这样好像更容易理解
@WanrenDing 因为这道题每个位置必定占有一定权重w[i]不可能为0，所以preSum里不会有重复元素，那么二分找到的第一个位置必然就是左侧边界了；返回值left能保证是target应插入preSum的位置的原因是我们取的是左闭右开的区间，left会移动至mid的右边一位，所以能保证left最终落在恰好比target大的位置（当然你return right也行）
请问有朋友用 Python 写的吗 我发现一个问题，就是在随机生成数字的时候，用以下这个是正确的
num = random.uniform(0, self.pre_sum[-1]) + 1
但是用 randint 在 leetcode 上跑就会报错
num = random.randint(0, self.pre_sum[-1]) + 1
LC528 Python 解法 左右闭合边界
注意由于是随机pick index，故测试结果可有多种
class Solution:
def __init__(self, w: List[int]):
#initialize the prefix sum
self.pre_sum = [0] * (len(w) + 1)
for i in range(len(w)):
self.pre_sum[i + 1] = self.pre_sum[i] + w[i]
def pickIndex(self) -> int:
#the range of random values is [1, self.pre_sum[-1]]
rand = random.randint(1, self.pre_sum[-1])
#binary search of 'rand' in the array 'pre_sum'
left, right = 1, len(self.pre_sum) - 1
#closed right interval, [left, right]
while left <= right:
mid = left + (right - left) // 2
if self.pre_sum[mid] > rand:
right = mid - 1
elif self.pre_sum[mid] < rand:
left = mid + 1
elif self.pre_sum[mid] == rand:
#Key point: fix left bound
right = mid - 1
return left - 1
前缀数组下标为0开始的，left_bound 两边闭合 java版本
class Solution {
private int[] preSum;
private Random rand = new Random();
public Solution(int[] w) {
preSum = new int[w.length];
preSum[0] = w[0];
// 获取前缀和
for (int i = 1; i < w.length; i++) {
preSum[i] = preSum[i - 1] + w[i];
}
}
public int pickIndex() {
int n = preSum.length;
// 在闭区间 [1, (preSum[n - 1] + 1)] 中随机一个数字
int target = rand.nextInt(preSum[n - 1]) + 1;
// 获取 target 在前缀和数组 preSum 中的索引
return left_bound(preSum, target);
}
// 向左边界靠拢
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;
}
}
// 因为返回的是 left 所以只考虑left出界的情况
// left出界
if (left >= nums.length) {
return left - 1;
}
return left;
}
}
class Solution {
public:
vector<long long> presum; //从0累加到i-1的和
Solution(vector<int>& w) {
presum = vector<long long>(w.size() + 1, 0);
for(int i = 1; i <= w.size(); ++i) {
presum[i] = presum[i-1] + w[i-1];
}
}
int pickIndex() {
int r = rand() % presum.back();
long long left = 0, right = presum.size() - 1;
while(left <= right) {
long long mid = left + (right - left) / 2;
if(presum[mid] <= r) left = mid + 1;
else if(presum[mid] > r) right = mid - 1;
}
return left - 1;
}
};
@billgoo， python中的randint(a,b)是能够取到b的，java中的random应该是不包括右边的值的。所以java中需要+1，python中不用。
Java, 0-indexed binary search
class Solution {
private int[] sums;
private int sum;
private Random random;
public Solution(int[] w) {
sums = new int[w.length];
random = new Random();
sum = 0;
for(int i = 0; i < w.length; i++) {
sum += w[i];
sums[i] = sum;
}
}
public int pickIndex() {
int value = random.nextInt(sum);
int index = binarySearch(sums, value);
if(sums[index] == value) {
return index+1;
}
return index;
}
private int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while(left < right) {
int mid = left + (right - left)/2;
if(array[mid] == target) {
return mid;
} else if(array[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
随机数取到 [1, sum[w]] 好像不是因为前缀和的数组有个[0]占位; 随机数取 [1, sum[w]] 对应找左边界，如果 [0, sum[w] - 1] 会使最左边多占一份，而最右边少占一份； 随机数取 [0, sum[w] - 1] 对应找右边界+1，如果 [1, sum[w]] 会使最左边少占一份，最右索引溢出。
我是用二分查找搜索右边界然后减了1，原理和东哥讲的一样，代码如下：
import java.util.Random;
class Solution {
int[] preSum;
int n;
public Solution(int[] w) {
this.n=w.length;
this.preSum=new int[n+1];
for(int i=0;i<n;i++){
preSum[i+1]=preSum[i]+w[i];
}
}
public int pickIndex() {
Random random=new Random();
int rand=random.nextInt(preSum[n])+1;//生成[1,preSum[n]]的随机数
return binRightBorder(preSum,rand);
}
private int binRightBorder(int[] preSum,int target){
int left=1,right=preSum.length-1;//left=1是因为preSum[0]肯定不是我们要找的
while(left<=right){
int mid=left+(right-left)/2;
if(preSum[mid]==target){
left=mid+1;
}else if(preSum[mid]<target){
left=mid+1;
}else if(preSum[mid]>target){
right=mid-1;
}
}
//结束条件：left=right+1
if(preSum[right]==target) return right-1;//因为前缀和索引多一位，所以减一
else return left-1; //如果没找到，则left是第一个比target大的
}
}
请教一下大佬，就是如果target的生成范围是 [1,preSum[n-1]]，的，那 index=0 下标不就一直无法被选中了吗，例如教学例子中，您使用的 target 生成范围是 [1:7]，那么通过这个方法不就是只能选中 index=1,2,3这些下标吗，0号下标只有当 target < 1时才会被选中不是吗，这里好像有点不太理解，请大佬不吝赐教
@hlxs-c 0 号下标不需要被选中，看这个图：
如果能选中 0 号下标的话，可能的选择总数（分母）就是 8 了，而实际上应该是 1+3+2+1=7。
提个小意见，我觉得大家对random选择target那一步有疑问，是因为上面这个图有误导性。比如w[0]=1，其实是{1}这个点被分配了对应给w[0]，再比如w[1]=3，其实是{2,3,4}分配给了w[1]。
而作者的图中，“对区间进行了着色”，再加上例子中刚刚好w[0]=1，让人误解了好像是“[0,1]这个区间对应w[0]”，并且w[0]=1和random中为了取到右边界的而+1的1意义不同，但是数值上都是1，更导致大家不容易理解。
所以是否图中不对区间着色，或者用别的方式指示weight对应的“集合范围”更好呢？
