简介
记住如何使用C++11函数的话会很简单.
参考链接
code
class Solution {
public:
vector<int> presum;
// 求前缀和
Solution(vector<int>& w): presum(move(w)) {
partial_sum(presum.begin(), presum.end(), presum.begin());
}
int pickIndex() {
int pos = (rand() % presum.back()) + 1;
return lower_bound(presum.begin(), presum.end(), pos) - presum.begin();
}
};
class Solution {
List<Integer> psum = new ArrayList<>();
int tot = 0;
Random rand = new Random();
public Solution(int[] w) {
for (int x : w) {
tot += x;
psum.add(tot);
}
}
public int pickIndex() {
int targ = rand.nextInt(tot);
int lo = 0;
int hi = psum.size() - 1;
while (lo != hi) {
int mid = (lo + hi) / 2;
if (targ >= psum.get(mid)) lo = mid + 1;
else hi = mid;
}
return lo;
}
}