528. Random Pick with Weight index的随机发生器

［抄题］：

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]

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道怎么找index

［英文数据结构或算法，为什么不用别的数据结构或算法］：

二分查找index，最后还要在区间内讨论区间的讨论需要带等号，从而返回一个整数

［一句话思路］：

把index和数字对应起来：在weightsum数组里搜索随机生成的weightsum，然后返回位置。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

找index的二分要考虑相等的情况, 此时end = mid

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

把index和数字对应起来：在weightsum数组里搜索随机生成的weightsum，然后返回位置。

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {

    Random random;

    int[] w;

    public Solution(int[] w) {

        //change the w to weightedsum

        this.random = random;

        for (int i = 1; i < w.length; i++) {

            w[i] += w[i - 1];

        }

        this.w = w;

    }

    public int pickIndex() {

        //initilization

        int start = 0; int end = w.length - 1;

        int randomSum = random.nextInt(w[w.length - 1]) + 1;

        //search for a range

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (w[mid] == randomSum) {

                end = mid;

            }

            if (w[mid] > randomSum) {

                end = mid;

            }if (w[mid] < randomSum) {

                start = mid;}

        }

        //search for the position

        if (randomSum <= w[start]) return start;

        else if (randomSum > w[end]) return end + 1;

        else if (randomSum <= w[end]) return end;

        return -1;

    }

}

/**

 * Your Solution object will be instantiated and called as such:

 * Solution obj = new Solution(w);

 * int param_1 = obj.pickIndex();

 */

巴特西

528. Random Pick with Weight index的随机发生器

最新文章

热门文章