{"id":3339,"date":"2018-07-28T17:08:09","date_gmt":"2018-07-29T00:08:09","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3339"},"modified":"2018-07-28T17:50:50","modified_gmt":"2018-07-29T00:50:50","slug":"leetcode-880-random-pick-with-weight","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-880-random-pick-with-weight\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 880. Random Pick with Weight"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given an array\u00a0w<\/code>\u00a0of positive integers, where\u00a0w[i]<\/code>\u00a0describes the weight of index\u00a0i<\/code>,\u00a0write a function\u00a0pickIndex<\/code>\u00a0which randomly\u00a0picks an index\u00a0in proportion\u00a0to its weight.<\/p>\n

Note:<\/p>\n

    \n
  1. 1 <= w.length <= 10000<\/code><\/li>\n
  2. 1 <= w[i] <= 10^5<\/code><\/li>\n
  3. pickIndex<\/code>\u00a0will be called at most\u00a010000<\/code>\u00a0times.<\/li>\n<\/ol>\n

    Example 1:<\/strong><\/p>\n

    Input: \r\n<\/strong>[\"Solution\",\"pickIndex\"]\r\n<\/span>[[[1]],[]]<\/span>\r\nOutput: <\/strong>[null,0]<\/span>\r\n<\/pre>\n
    \n
    Example 2:<\/strong><\/p>\n
    Input: \r\n<\/strong>[\"Solution\",\"pickIndex\",\"pickIndex\",\"pickIndex\",\"pickIndex\",\"pickIndex\"]\r\n<\/span>[[[1,3]],[],[],[],[],[]]<\/span>\r\nOutput: <\/strong>[null,0,1,1,1,0]<\/span><\/pre>\n<\/div>\n
    Explanation of Input Syntax:<\/strong><\/p>\n
    The input is two lists:\u00a0the subroutines called\u00a0and their\u00a0arguments.\u00a0Solution<\/code>‘s\u00a0constructor has one argument, the\u00a0array\u00a0w<\/code>.\u00a0pickIndex<\/code>\u00a0has no arguments.\u00a0Arguments\u00a0are\u00a0always wrapped with a list, even if there aren’t any.<\/p>\n
    Solution: Binary Search<\/strong><\/h1>\n
      \n
    1. Convert PDF to CDF<\/li>\n
    2. Uniformly sample a value s in [1, sum(weights)].<\/li>\n
    3. Use binary search to find first index such that PDF[index] >= s.<\/li>\n<\/ol>\n
      Time complexity: Init O(n), query O(logn)<\/p>\n
      Space complexity: O(n)<\/p>\n
      C++<\/p>\n
      \/\/ Author: Huahua\r\n\/\/ Running time: 184 ms\r\nclass Solution {\r\npublic:\r\n  Solution(vector<int> w) { \r\n    sums_ = std::move(w);\r\n    for (int i = 1; i < sums_.size(); ++i)\r\n      sums_[i] += sums_[i - 1];\r\n  }\r\n\r\n  int pickIndex() {\r\n    int s = rand() \/ static_cast<double>(RAND_MAX) * sums_.back() + 1;\r\n    return lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();\r\n    \/\/ or\r\n    \/\/ int l = 0;\r\n    \/\/ int r = sums_.size();\r\n    \/\/ while (l < r) {\r\n    \/\/   int m = (r - l) \/ 2 + l;\r\n    \/\/   if (sums_[m] < s)\r\n    \/\/     l = m + 1;\r\n    \/\/   else\r\n    \/\/     r = m;\r\n    \/\/ }\r\n    \/\/ return l;\r\n  }\r\nprivate:  \r\n  vector<int> sums_;\r\n};<\/pre>\n
      Related Problems<\/strong><\/h1>\n