题目描述
Given an array w
of positive integers, where w[i]
describes the weight of index i
, write a function pickIndex
which randomly picks an index in proportion to its weight.
Note:
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex
will be called at most10000
times.
样例
Example 1:
Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]
Example 2:
Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution
‘s constructor has one argument, the array w
. pickIndex
has no arguments. Arguments are always wrapped with a list, even if there aren’t any.
题意是给定一个权重数组,根据权重占整体的比例(记为p
),通过函数pickIndex
以概率p
返回其对应的下标。描述很拗口,就以第二个样例作为例子:
给定权重数组1,3
,其中1
占整体的比例为1/4
,3占整体的比例为3/4
,那么函数pickIndex
应该以1/4
的概率返回0(对应1的下标),以3/4
的概率返回下标1
。
不妨设权重总和为total
,那么我们生成0-total - 1
之间的整数,实际上就可以根据权重来对数字进行划分:
0 | 1 2 3
随机数生成器等概率的生成0-3之间的数字,那么假如生成的数字为0,就返回下标0,生成1或2或3,就返回下标1,这样就满足根据权重返回下标了。
为了确定数字和下标对应的关系,我们需要计算前缀和:
前缀和下标: 0 1 2
前缀和数据: 0 1 4
实际上确定对应关系就是根据前缀和数据查找第一个大于数字的值,用其在前缀和的下标然后减一。比如生成数字2,查找到的位置是4对应的下标2,pickIndex
就返回2-1
,查找过程很容易就联想到利用二分法。
回顾一下随机数生成器,rand()
生成0到INT_MAX
之间的整数,如果随机数种子不变,每次生成的结果是一致的,比如可以试试下面的输出结果是不是
83 86 77 15 93 35 86 92 49 21
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 10; ++i) {
cout << (rand() % 100) << ' ';
}
cout << endl;
return 0;
}
srand(timeNULL)
实际上是利用系统时间来初始化随机数种子,这样每次获得的序列是不同的。貌似LeetCode
的题目是不能让每次获得序列不同,不然就没法评测了。
C++ 代码
class Solution {
vector<int> preSum;
int n;
public:
Solution(vector<int>& w) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
n = w.size();
preSum.resize(n + 1, 0);
for (int i = 1; i <= n; ++i) {
preSum[i] = preSum[i - 1] + w[i - 1];
}
}
int pickIndex() {
//srand(time(NULL));
int total = preSum[n];
int target = rand() % total;
int res = upper_bound(preSum.begin() + 1, preSum.end(), target) - preSum.begin();
return res - 1;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(w);
* int param_1 = obj->pickIndex();
*/