528. Random Pick with Weight.md

528. Random Pick with Weight

---

Difficulty : Medium

Related Topics : Random、Binary Search

---

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

For example, given an input list of values [1, 9], when we pick up a number out of it, the chance is that 9 times out of 10 we should pick the number 9 as the answer.

Example 1:

Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Constraints:

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10^5
• pickIndex will be called at most 10000 times.

---

Solution

• mine

  • Java

---

• Knuth shuffle
• Fisher–Yates shuffle

---

• the most votes

• PreSum & BinarySearch Runtime: 32 ms, faster than 27.98%,Memory Usage: 53.2 MB, less than 14.04% of Java online submissions

  // O(N)time O(N)space
  // pickIndex → O(logN)time
  int[] sum;
  int len;
  Random random;
  
  public Solution(int[] w) {
      random = new Random();
      for (int i = 1; i < w.length; i++) {
          w[i] = w[i] + w[i - 1];
      }
      sum = w;
      len = sum.length;
  }
  
  public int pickIndex() {
      int idx = random.nextInt(sum[len - 1]) + 1;
      int left = 0, right = len - 1;
      while (left < right) {
          int mid = left + (right - left) / 2;
          if (sum[mid] == idx)
              return mid;
          else if (sum[mid] < idx)
              left = mid + 1;
          else
              right = mid;
      }
      return left;
  }
  

---

• leetcode solution

• PreSum & BinarySearch Runtime: 43 ms, faster than 23.22%, Memory Usage: 54.4 MB, less than 5.06% of Java online submissions

  // O(N)time O(N)space
  // pickIndex → O(logN)time
  
  List<Integer> psum = new ArrayList<>();
  int tot = 0;
  Random rand = new Random();
  
  public Solution(int[] w) {
      for (int x : w) {
          tot += x;
          psum.add(tot);
      }
  }
  
  public int pickIndex() {
      int targ = rand.nextInt(tot);
  
      int lo = 0;
      int hi = psum.size() - 1;
      while (lo != hi) {
          int mid = (lo + hi) / 2;
          if (targ >= psum.get(mid)) lo = mid + 1;
          else hi = mid;
      }
      return lo;
  }
  

---