class Solution {
int[] indexArray;
int length = 0;
public Solution(int[] w) {
indexArray = new int[w.length];
indexArray[0] = w[0];
length = w[0];
for (int j = 1; j < w.length; j++) {
length += w[j];
indexArray[j] = w[j] + indexArray[j - 1];
}
}
public int pickIndex() {
int index = (int) (Math.random() * length) + 1;
return binarySearch(index);
}
private int binarySearch(int index) {
int low = 0;
int high = indexArray.length;
while (low < high) {
int bet = low + (high - low) / 2;
if (indexArray[bet] > index) {
high = bet;
} else if (indexArray[bet] < index){
low = bet + 1;
} else {
return bet;
}
}
return low;
}
}
解题思路：
1、读题我想到的第一种方式是构造一个能装下所有值的数组，然后获取随机数返回对应下标的值：
class Solution {
int[] indexArray;
int length = 0;
public Solution(int[] w) {
// 获取长度
for (int i = 0; i < w.length; i++) {
length += w[i];
}
indexArray = new int[length];
int start = 0;
// 将对应值放入对应下标的位置
for (int j = 0; j < w.length; j++) {
Arrays.fill(indexArray, start, start + w[j], j);
start += w[j];
}
}
public int pickIndex() {
int index = (int) (Math.random() * length) + 1;
return indexArray[index];
}
}
果不其然，内存超了！
2、
- 使用前缀和构造数组，该数组定然是递增数组，最后一位为 length, 获取的随机值也定然在数组的区间之内。
- 通过传入的随机值进行二分查询定位值在哪个区间（要么能对应上，要么在两个值之间），向下取值。
3、数学概念偏多，记录一下，以后复习。前缀和可以重点联系下
