528. Random Pick with Weight

Question

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.

Note:

  • 1 <= w.length <= 10000
  • 1 <= w[i] <= 10^5
  • pickIndex will be called at most 10000 times.
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.

Solutions:

  • Method 1: O(n) for each pick 
      class Solution {
      private static Random random = new Random();
      private int[] w;
      private int sum;
      public Solution(int[] w) {
          this.w = w;
          for(int num : w) this.sum += num;
      }
        
      public int pickIndex() {
          int rand = random.nextInt(sum) + 1;
          int temp = 0;
          for(int i = 0; i < w.length; i++){
              if(temp + w[i] >= rand) return i;
              temp += w[i];
          }
          return w.length - 1;
      }
  }
    
  /**
   * Your Solution object will be instantiated and called as such:
   * Solution obj = new Solution(w);
   * int param_1 = obj.pickIndex();
   */
  • Method 2: Binary search O(lgN)
    • we take the sum up to all indexes.

    • we use binary search to find the first number bigger(or equal to) the random value. ```Java class Solution { private static Random random = new Random(); private int[] w; public Solution(int[] w) { this.w = w; for(int i = 1; i < w.length; i++){ w[i] += w[i - 1]; } }

      public int pickIndex() { int rand = random.nextInt(w[w.length - 1]) + 1; int left = 0, right = w.length - 1; while(left < right){ int mid = left + (right - left) / 2; if(w[mid] == rand) return mid; else if(w[mid] < rand) left = mid + 1; else right = mid; } return left; } }

    /**

    • Your Solution object will be instantiated and called as such:
    • Solution obj = new Solution(w);
    • int param_1 = obj.pickIndex(); */ ```