LeetCode //C - 528. Random Pick with Weight

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 528. Random Pick with Weight。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

528. Random Pick with Weight

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i t h i^{th} ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

  • For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
     
Example 1:

Input:
[“Solution”,“pickIndex”]
[[[1]],[]]
Output:
[null,0]
Explanation:
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2:

Input:
[“Solution”,“pickIndex”,“pickIndex”,“pickIndex”,“pickIndex”,“pickIndex”]
[[[1,3]],[],[],[],[],[]]
Output:
[null,1,1,1,1,0]
Explanation:
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]

and so on.

Constraints:
  • 1 < = w . l e n g t h < = 1 0 4 1 <= w.length <= 10^4 1<=w.length<=104
  • 1 < = w [ i ] < = 1 0 5 1 <= w[i] <= 10^5 1<=w[i]<=105
  • pickIndex will be called at most 1 0 4 10^4 104 times.

From: LeetCode
Link: 528. Random Pick with Weight


Solution:

Ideas:

1. Initialization (solutionCreate):

  • Compute a prefix sum array from the given weights. This allows us to efficiently map a random number to an index based on the weights.
  • Store this prefix sum and the total sum of weights for later use during the pick index operation.

2. Pick Index (solutionPickIndex):

  • Generate a random number within the range [1, total weight].
  • Use a binary search on the prefix sum array to find the smallest index where the prefix sum is greater than or equal to the random number. This step ensures that the probability of picking an index is proportional to its weight.

3 .Clean Up (solutionFree):文章来源地址https://www.toymoban.com/news/detail-855489.html

  • Free up the memory used by the solution object, including the dynamically allocated prefix sum array.
Code:
typedef struct {
    int* prefixSums;
    int totalWeight;
    int length;
} Solution;

Solution* solutionCreate(int* w, int wSize) {
    Solution* obj = (Solution*) malloc(sizeof(Solution));
    obj->prefixSums = (int*) malloc(wSize * sizeof(int));
    obj->length = wSize;
    obj->totalWeight = 0;
    
    for (int i = 0; i < wSize; i++) {
        obj->totalWeight += w[i];
        obj->prefixSums[i] = obj->totalWeight;
    }
    
    return obj;
}

int solutionPickIndex(Solution* obj) {
    int target = rand() % obj->totalWeight + 1;
    int low = 0, high = obj->length - 1;
    
    // Binary search to find the lowest index where the prefix sum is >= target
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (obj->prefixSums[mid] < target)
            low = mid + 1;
        else
            high = mid;
    }
    
    return low;
}

void solutionFree(Solution* obj) {
    free(obj->prefixSums);
    free(obj);
}

到了这里,关于LeetCode //C - 528. Random Pick with Weight的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode with Golang 滑动窗口 Part1

    滑动窗口的定义: 滑动窗口这一个技巧主要运用于处理数组问题上,一般用于“子串”问题。精髓是,维护一个里面装着元素的“窗口”,在将新元素装进“窗口”的同时,根据题意,把不符合题意的元素踢出“窗口”。 滑动窗口的模板: 接下来看几道题目: Leetcode 209.长

    2024年01月19日
    浏览(44)
  • LeetCode992. Subarrays with K Different Integers

    Given an integer array nums and an integer k, return the number of good subarrays of nums. A good array is an array where the number of different integers in that array is exactly k. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. A subarray is a contiguous part of an array. Example 1: Input: nums = [1,2,1,2,3], k = 2 Output: 7 Explanation: S

    2024年01月20日
    浏览(38)
  • Leetcode 357. Count Numbers with Unique Digits

    Given an integer n, return the count of all numbers with unique digits, x, where 0 = x 1 0 n 0 = x 10^n 0 = x 1 0 n . f(0) = 1 f(1) = 10 f(k) = 9 * 9 * 8 * … * (9 - k + 2)

    2024年02月19日
    浏览(45)
  • LeetCode2085. Count Common Words With One Occurrence

    Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays. Example 1: Input: words1 = [“leetcode”,“is”,“amazing”,“as”,“is”], words2 = [“amazing”,“leetcode”,“is”] Output: 2 Explanation: “leetcode” appears exactly once in each of the two arrays. We count this s

    2024年01月16日
    浏览(40)
  • 【贪心】个人练习-Leetcode-2195. Append K Integers With Minimal Sum

    题目链接:https://leetcode.cn/problems/append-k-integers-with-minimal-sum/ 题目大意:给出一个数组 nums[] ,现在要往里面追加 k 个【互不相同】且【未出现在 nums[] 中】的【正整数】,使得这 k 个数字之和最小。 思路:明显就是贪心,从 1 开始塞进去即可。但是单纯的【累加+用set判断是

    2024年02月02日
    浏览(48)
  • leetcode - 1293. Shortest Path in a Grid with Obstacles Elimination

    You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possib

    2024年02月08日
    浏览(43)
  • LeetCode 2441. Largest Positive Integer That Exists With Its Negative【哈希集合】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月05日
    浏览(41)
  • Leetcode 1325. Delete Leaves With a Given Value (二叉树后序遍历经典题)

    Delete Leaves With a Given Value Solved Medium Topics Companies Hint Given a binary tree root and an integer target, delete all the leaf nodes with value target. Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot)

    2024年02月22日
    浏览(46)
  • D. Problem with Random Tests

    Problem - 1743D - Codeforces   思路:因为是或,所以答案一定会比原串更大,并且为了保留更多的1,我们可以选择原串作为其中一个串,另一个串则要找到第一个为0的位置,我们希望让这个为1,为了让这个位置在或之后为1,需要满足两个条件,假设这个位置为id,那么首先要满

    2024年02月12日
    浏览(43)
  • LeetCode 865. Smallest Subtree with all the Deepest Nodes【树,DFS,BFS,哈希表】1534

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包