要求: 返回的随机函数的时间复杂度不超过 O(logn)。...例如对于数组 w[1,3,5,6],计算其累计的前缀和数组为 [1,4,9,15],然后随机产生一个 [1,15] 之间的随机数。...如果随机数落在 [1,1],应该找到的值为 1, 对应元素下标为 0,
如果随机数落在 [2,4] 区间,应该找到值 4, 对应元素下标为 1,
如果随机数落在 [5,9] 区间,应该找到值 9,...复杂度分析:
时间复杂度:初始化的时间复杂度为 O(n),每次选择的时间复杂度为 O(logn),其中 n 是数组 w 的长度。
空间复杂度:O(n),即前缀和数组需要使用的空间。...按权重随机选择 - leetcode