This is a question of the day from LeetCode 2021-8-30: “528. Randomly selected by weight”

1. Topic description

Given an array of positive integers w, where w[I] represents the weight of subscript I (subscripts start at 0), write a function pickIndex that randomly picks subscript I with a probability that is proportional to w[I].

For example, for w = [1, 3], the probability of choosing subscript 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), while the probability of choosing subscript 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

In other words, the probability of picking subscript I is w[I] / sum(w).

Example 1:

Input: ["Solution","pickIndex"] [[[1]] output: [null,0] explanation: Solution Solution = new Solution([1]); solution.pickIndex(); // Return 0, since there is only one element in the array, the only option is to return the index 0.Copy the code

Example 2:

Input: [" Solution ", "pickIndex", "pickIndex", "pickIndex", "pickIndex", "pickIndex"] [[[1, 3]], [], [], [], [], []] output: [null,1,1,1,1,0] [null,1,1,1, 0] solution.pickIndex(); // Returns 1, returns subscript 1 with probability 3/4. solution.pickIndex(); // Return 1 solution.pickindex (); // Return 1 solution.pickindex (); // Return 1 solution.pickindex (); // Returns 0, returns subscript 0 with probability 1/4. Since this is a random question, allowing for multiple answers, the following output can be considered correct: [null, 1,1,1,1,0] [null, 1,1,1,1,1] [null, 1,1,1,0,0] [null, 1,1,1,0,1] [null, 1,0,1,0,0]... So on.Copy the code

2. Answer

Input array for [1, 2, 3, 4], for example, is divided into: [1, 1], [2, 3], [4 and 6], [7,8,9,10], calculate the prefix and array,3,6,10 [1].

Generates a random integer between [1,10], uses binary lookup to find the minimum subscript I in the prefix and array that satisfies the interval condition, and returns.

class Solution {
    constructor(w) {
        this.len = w.length;
        // Define prefixes and arrays
        this.pre = new Array(this.len).fill(0);
        this.pre[0] = w[0];
        // Start with I =1 and find the prefix sum for each position
        for (let i = 1; i < this.len; i++) {
            this.pre[i] = this.pre[i - 1] + w[i];
        }
        console.log(this.pre);
        / / the sum
        this.total = this.pre[this.len - 1];
    }
    pickIndex() {
        Math.random() returns a random number between 0 and 1
        // x is a random integer between 1 and total
        const x = Math.floor(Math.random() * this.total) + 1;
        // Binary search
        let [low, high] = [0.this.len - 1];
        while (low <= high) {
            const mid = (low + high) >> 1;
            if (this.pre[mid] < x) low = mid + 1;
            else high = mid - 1;
        }
        returnlow; }}Copy the code

has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

Warehouse address: “One of the Day series”