[LeetCode] 528. Random Pick with Weight

wangjuntytl 发布于2019-08-16 13:40 / 1532人阅读

Problem

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.

Solution

create an array sum, to save sum of weights

create a Random random to create random in a range

the range should be [1, maxValue] as [1, sum[len-1]]

use Random.nextInt(maxValue) + 1 to get a random num of the range

use binary search to find the index of random in sum array

class Solution {
    int[] sums;
    int max;
    Random random;
    public Solution(int[] w) {
        sums = new int[w.length];
        sums[0] = w[0];
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i-1]+w[i];
        }
        max = sums[sums.length-1];
        random = new Random();
    }
    
    public int pickIndex() {
        int rand = random.nextInt(max)+1;
        int index = findIndex(sums, rand);
        return index;
    }
    
    private int findIndex(int[] nums, int k) {
        int start = 0, end = nums.length-1;
        while (start+1 < end) {
            int mid = start+(end-start)/2;
            if (nums[mid] == k) return mid;
            else if (nums[mid] < k) start = mid+1;
            else end = mid-1;
        }
        if (k > nums[end]) return end+1;
        else if (k > nums[start]) return start+1;
        else return start;
    }
}

超融合服务器混合云 pick Weight LeetCode font-weight

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72117.html

[LeetCode] 398. Random Pick Index (Reservoir Sampl

Problem Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note:The array siz...

edagarli 2019-08-16 13:46 评论0 收藏0
leetcode398. Random Pick Index

摘要：思路一的实现其实要是想在的时间内完成随机数的获取，只需要缓存每个数字出现的下标，但是这意味着需要先对数据进行遍历，并且还需要的空间来额外存储数字下标的集合。所以我们只能每次在获取数字的时候来统计数字出现的次数，然后针对次数获取随机数下标。题目要求 Given an array of integers with possible duplicates, randomly output ...

airborne007 2019-08-16 15:07 评论0 收藏0
leetcode382. Linked List Random Node

摘要：题目要求要求从单链表中，随机返回一个节点的值，要求每个节点被选中的概率是相等的。假如一共有个物品，需要从其中挑选出个物品，要求确保个物品中每个物品都能够被等概率选中。对于这种等概率问题，简答的做法是通过随机数获取选中物品的下标。题目要求 Given a singly linked list, return a random nodes value from the linked li...

xiaodao 2019-08-16 17:58 评论0 收藏0
三维重建工具——pclpy教程之八叉树的空间分区和搜索操作

摘要：在本教程中，我们将学习如何使用八叉树在点云数据中进行空间分区和邻居搜索。因此，搜索点和搜索结果之间的距离取决于八叉树的分辨率参数。此外，先进的内存管理减少了八叉树构建过程中的内存分配和释放操作。总结八叉树实现是空间分区和搜索操作的强大工具。本教程代码开源：GitHub 欢迎st...

番茄西红柿 2021-11-26 11:11 评论0 收藏2637
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大体意思就是，先复制到，顺便将所有的放在再复制所有的到，顺便将所有的放在最后令，令，将和分离，返回的头结点 Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...

Jacendfeng 2019-08-14 15:32 评论0 收藏0