| 12345678910111213141516171819202122232425262728293031323334353637 |
- type Solution struct {
- sum []int
- l int
- n int
- }
- func Constructor(w []int) (sol Solution) {
- n := len(w)
- sol.sum = make([]int, n+1)
- for i := range w {
- sol.sum[i+1] = sol.sum[i] + w[i]
- }
- sol.n, sol.l = sol.sum[n], n+1
- return
- }
- func (this *Solution) PickIndex() int {
- idx := rand.Intn(this.n) + 1
- beg, end := 1, this.l-1
- for beg <= end {
- mid := beg + (end - beg)
- if val := this.sum[mid]; val == idx {
- return mid - 1
- } else if val < idx {
- beg = mid + 1
- } else {
- end = mid - 1
- }
- }
- return beg - 1
- }
- /**
- * Your Solution object will be instantiated and called as such:
- * obj := Constructor(w);
- * param_1 := obj.PickIndex();
- */
|
