This is the 30th day of my participation in the August Challenge

Leetcode -528- Randomly assigned by weight

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

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] <= 10^5
  • PickIndex will be called no more than 10,000 times

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Statistical probability

  • Fixed interval, generate random number, and then binary search interval
  • The problem is too vague
  • The overall difficulty is the understanding of the questions
  • And when you look at the solution, you see that you need a result set that basically conforms to the probability distribution
  • The prefix and can be used to get the range represented by each index
  • The purpose of the pickIndex function is to get the index value that falls in a different range each time
  • Index range 0-> N -1
  • A weight value is obtained by random random number, and its corresponding range can be found by binary search
  • Then return the index location
  • Because the number range is small, violent search can also be, binary search does not need to consider the binary scope of the boundary
int[] sum;
Random random = new Random();

public Solution(int[] w) {
    sum = w;
    for (int i = 1; i < sum.length; i++) {
        sum[i] += sum[i - 1]; }}public int pickIndex(a) {
    int i = random.nextInt(sum[sum.length - 1]) + 1;
    return binarySearch(i);
}

public int binarySearch(int i) {
    int l = 0, r = sum.length - 1;
    while (l < r) {
        int mid = l + r  >> 1;
        if (sum[mid] >= i) {
            r = mid;
        } else {
            l = mid + 1; }}return l;
}
Copy the code
  • Initialization: time complexity O(n); PickIndex time complexity O(LGN)
  • Space complexity O(n)