资讯专栏INFORMATION COLUMN

[LeetCode] 528. Random Pick with Weight

wangjuntytl / 1680人阅读

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;
    }
}

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

转载请注明本文地址: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 评论0 收藏0
  • leetcode398. Random Pick Index

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

    airborne007 评论0 收藏0
  • leetcode382. Linked List Random Node

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

    xiaodao 评论0 收藏0
  • 三维重建工具——pclpy教程之八叉树的空间分区和搜索操作

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

    番茄西红柿 评论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 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<