[LeetCode] 528. Random Pick with Weight

wangjuntytl 發布于2019-08-16 13:40 / 1681人閱讀

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

云服務器 GPU云服務器 pick Weight LeetCode font-weight

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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