This is the 30th day of my participation in the August Text Challenge.More challenges in August

Topic describes

This is 528 on LeetCode. Randomly selected by weight, medium difficulty.

Tag: “prefix and”, “dichotomy”, “simulation”

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 picking subscript 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), while the probability of picking 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

Tip:

  • 1 <= w.length <= 10000
  • 1 <= w[i] <=
    1 0 5 10^5
  • PickIndex will be called no more than 10,000 times

Prefix and + dichotomy

[I]∑ I = 0W. length−1w[I]\sum_{I =0}^{w.length-1} w[I]∑ I = 0W. length−1w[I] Number of returns of subscript iii.

The generation of random numbers can directly use the language’s own API, the rest of us need to construct a distribution in accordance with the weight of the sequence.

Since 1<=w[I]<=1051 <= W [I]<=10 ^51<= W [I]<=105, and the WWW length is 10410^4104, a number of iii with w[I]w[I]w[I] would be MLE directly.

We can use the prefix and array as the weight distribution sequence, the basic unit of the weight sequence is
1 1 .

A constructed “prefix and” array of length NNN can be seen as a number line of [1,sum[n−1]][1, sum[n-1]] with basic unit 111.

Random numbers within the range [1,sum[n−1]][1, sum[n-1]][1,sum[n−1]] are generated using random function parameters. The original subscript values corresponding to distribution positions can be found by using the “binary” prefix and array.

Code:

class Solution {
    int[] sum;
    public Solution(int[] w) {
        int n = w.length;
        sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + w[i - 1];
    }
    
    public int pickIndex(a) {
        int n = sum.length;
        int t = (int) (Math.random() * sum[n - 1]) + 1;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum[mid] >= t) r = mid;
            else l = mid + 1;
        }
        return r - 1; }}Copy the code
  • Time complexity:SolutionClass constructor overall complexity is
    O ( n ) O(n)     ;pickIndexIs the complexity of
    O ( log ⁡ n ) O(\log{n})
  • Space complexity: O(n)O(n)O(n)

Simulation (bucket polling)

Using OJ not too clever (an approximate check of the weight distribution), we can construct a minimum polling sequence (the weight accuracy is reserved to one decimal place) and store it in the form of (I, CNT)(I, CNT)(I, CNT), representing the subscript III in the minimum polling sequence as CNTCNTCNT.

The bucket is then polled back using two numbers bidbidbid and iidiidiID (loop reset & skip to next bucket).

The biggest advantage of this solution is that random function is not needed, and the returned continuous sequence satisfies the approximate weight distribution of each segment (length not shorter than the minimum segment).

Code:

class Solution {
    // Bucket number/bucket number/total number
    int bid, iid, tot;
    List<int[]> list = new ArrayList<>();
    public Solution(int[] w) {
        int n = w.length;
        double sum = 0, min = 1e9;
        for (int i : w) {
            sum += i;
            min = Math.min(min, i);
        }
        double minv = min / sum;
        int k = 1;
        while (minv * k < 1) k *= 10;
        for (int i = 0; i < n; i++) {
            int cnt = (int)(w[i] / sum * k);
            list.add(new int[]{i, cnt}); tot += cnt; }}public int pickIndex(a) {
        if (bid >= list.size()) {
            bid = 0; iid = 0;
        }
        int[] info = list.get(bid);
        int id = info[0], cnt = info[1];
        if (iid >= cnt) {
            bid++; iid = 0;
            return pickIndex();
        }
        iid++;
        returnid; }}Copy the code
  • Time complexity: computation
    k k     The operation of, which occurs only once, can be regarded as a constant calculation amortized to each subscript,SolutionThe overall complexity of the constructor of a class can be viewed as
    O ( n ) O(n)     ;pickIndexIs the complexity of
    O ( 1 ) O(1)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.528 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, so we will finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.