0528. Random Pick With Weight

# 528. Random Pick with Weight#

## 题目 #

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. `1 <= w.length <= 10000`
2. `1 <= w[i] <= 10^5`
3. `pickIndex` will be called at most `10000` 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.

## 题目大意 #

1. 1 <= w.length <= 10000
2. 1 <= w[i] <= 10^5
3. pickIndex 将被调用不超过 10000 次

## 解题思路 #

• 给出一个数组，每个元素值代表该下标的权重值，`pickIndex()` 随机取一个位置 i，这个位置出现的概率和该元素值成正比。
• 由于涉及到了权重的问题，这一题可以先考虑用前缀和处理权重。在 `[0,prefixSum)` 区间内随机选一个整数 `x`，下标 `i` 是满足 `x< prefixSum[i]` 条件的最小下标，求这个下标 `i` 即是最终解。二分搜索查找下标 `i` 。对于某些下标 `i`，所有满足 `prefixSum[i] - w[i] ≤ v < prefixSum[i]` 的整数 `v` 都映射到这个下标。因此，所有的下标都与下标权重成比例。
• 时间复杂度：预处理的时间复杂度是 O(n)，`pickIndex()` 的时间复杂度是 O(log n)。空间复杂度 O(n)。

## 代码 #

``````
package leetcode

import (
"math/rand"
)

// Solution528 define
type Solution528 struct {
prefixSum []int
}

// Constructor528 define
func Constructor528(w []int) Solution528 {
prefixSum := make([]int, len(w))
for i, e := range w {
if i == 0 {
prefixSum[i] = e
continue
}
prefixSum[i] = prefixSum[i-1] + e
}
return Solution528{prefixSum: prefixSum}
}

// PickIndex define
func (so *Solution528) PickIndex() int {
n := rand.Intn(so.prefixSum[len(so.prefixSum)-1]) + 1
low, high := 0, len(so.prefixSum)-1
for low < high {
mid := low + (high-low)>>1
if so.prefixSum[mid] == n {
return mid
} else if so.prefixSum[mid] < n {
low = mid + 1
} else {
high = mid
}
}
return low
}

/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(w);
* param_1 := obj.PickIndex();
*/

``````

Nov 25, 2022