528. Random Pick with Weight
Skills:
Prefix Sum
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu thiết kế một cấu trúc dữ liệu để chọn ngẫu nhiên một chỉ mục với xác suất tỷ lệ thuận với trọng số của nó
Approach - Prefix sum + Binary Search
w =[1][3][2] → prefix sum = [1][4][6].x trong khoảng [1, tổng trọng số]. Ví dụ: tổng w = 6 → x ∈[1][6].Solution - prefix sum & binary search
1class Solution {
2 private prefix: number[];
3 private total: number;
4
5 constructor(w: number[]) {
6 this.prefix = [0];
7 let current_sum = 0;
8 for (const weight of w) {
9 current_sum += weight;
10 this.prefix.push(current_sum);
11 }
12 this.total = current_sum;
13 }
14
15 pickIndex(): number {
16 const x = Math.floor(Math.random() * this.total) + 1;
17
18 let left = 0;
19 let right = this.prefix.length - 1;
20 while (left <= right) {
21 const mid = left + Math.floor((right - left) / 2);
22 if (this.prefix[mid] < x) {
23 left = mid + 1;
24 } else {
25 right = mid - 1;
26 }
27 }
28
29 return left - 1;
30 }
31}
32
33/**
34 * Your Solution object will be instantiated and called as such:
35 * var obj = new Solution(w)
36 * var param_1 = obj.pickIndex()
37 */