{"id":5613,"date":"2019-09-29T20:34:54","date_gmt":"2019-09-30T03:34:54","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5613"},"modified":"2019-09-29T20:37:37","modified_gmt":"2019-09-30T03:37:37","slug":"leetcode-528-random-pick-with-weight","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-528-random-pick-with-weight\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 528. Random Pick with Weight"},"content":{"rendered":"\n

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

Note:<\/p>\n\n\n\n

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

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

    Input: \n<\/strong>[\"Solution\",\"pickIndex\"]\n[[[1]],[]]\nOutput: <\/strong>[null,0]\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input: \n<\/strong>[\"Solution\",\"pickIndex\",\"pickIndex\",\"pickIndex\",\"pickIndex\",\"pickIndex\"]\n[[[1,3]],[],[],[],[],[]]\nOutput: <\/strong>[null,0,1,1,1,0]<\/pre>\n\n\n\n
    Explanation of Input Syntax:<\/strong><\/p>\n\n\n\n
    The input is two lists: the subroutines called and their arguments. Solution<\/code>‘s constructor has one argument, the array w<\/code>. pickIndex<\/code> has no arguments. Arguments are always wrapped with a list, even if there aren’t any.<\/p>\n\n\n\n
    Solution: Binary Search<\/strong><\/h2>\n\n\n\n
    Crate a cumulative weight array, random sample a “weight”, do a binary search to see which bucket that weight falls in.
    e.g. w = [2, 3, 1, 4], sum = [2, 5, 6, 10]
    sample 3 => index = 1
    sample 7 => index = 3<\/p>\n\n\n\n
    Time complexity: Init: O(n) Pick: O(logn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  Solution(vector w): sums_(std::move(w)) {\n    partial_sum(begin(sums_), end(sums_), begin(sums_));    \n  }\n\n  int pickIndex() {\n    int s = rand() % sums_.back();\n    return upper_bound(begin(sums_), end(sums_), s) - begin(sums_);\n  }\nprivate:  \n  vector sums_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177,91],"class_list":["post-5613","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","tag-random","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5613","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5613"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5613\/revisions"}],"predecessor-version":[{"id":5616,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5613\/revisions\/5616"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}