leetcode 398. Random Pick Index 均概率挑选index

怼烎@ 2022-06-04 06:28 47阅读 0赞

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 size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int\[\] nums = new int\[\] \{1,2,3,3,3\};  
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.  
solution.pick(3);

// pick(1) should return 0. Since in the array only nums\[0\] is equal to 1.  
solution.pick(1);

题意很简单，就是均匀概率的挑选相关index，我是网上看的做法，就这么做吧

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        vector<int> v;
        Solution(vector<int> nums) : v(nums) 
        {
    
        }
    
        int pick(int target) 
        {
            int cnt = 0, res = -1;
            for (int i = 0; i < v.size(); ++i) 
            {
                if (v[i] != target) 
                    continue;
                ++cnt;
                if (rand() % cnt == 0) res = i;
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关 Random Pick Index（C++随机数索引）

（1）map class Solution { private: unordered_map<int,vector<int>> mp;

- 日理万妓/ 2023年01月17日 08:28/ 0 赞/ 120 阅读

相关 leetcode 398. Random Pick Index | 398. 随机数索引（Java）

题目 [https://leetcode.com/problems/random-pick-index/][https_leetcode.com_problems_ran

忘是亡心i/ 2022年09月02日 01:17/ 0 赞/ 44 阅读

相关 leetcode 274. H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, w

缺乏、安全感/ 2022年08月20日 13:20/ 0 赞/ 158 阅读

相关 .index()

描述: 从匹配的元素中搜索给定元素的索引值，从0开始计数。添加的版本: [1.4][].index() 这个方法不接受任何参数。

本是古典何须时尚/ 2022年08月06日 15:20/ 0 赞/ 184 阅读

相关 leetcode 275. H-Index II

What if the `citations` array is sorted in ascending order? Could you optimize your algo

亦凉/ 2022年07月28日 08:35/ 0 赞/ 15 阅读

相关 [leetcode]274. H-Index/275. H-Index II -- JavaScript 代码

这道题的题目看了好久才看懂： H-Index其实是个用来比较学者学术成就的标准，某人的H-Index=x就表示在他所有的论文里，至少有x篇被引用了x次。本题来说：就是

「爱情、让人受尽委屈。」/ 2022年07月19日 05:19/ 0 赞/ 150 阅读

相关 leetcode:H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could y

向右看齐/ 2022年07月10日 06:28/ 0 赞/ 86 阅读

相关 leetcode： H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, w

缺乏、安全感/ 2022年07月10日 06:27/ 0 赞/ 75 阅读

相关 leetcode 398. Random Pick Index 均概率挑选index

Given an array of integers with possible duplicates, randomly output the index of a give

怼烎@/ 2022年06月04日 06:28/ 0 赞/ 48 阅读

相关 index

<!DOCTYPE html> <html> <head> <meta charset="utf-8" />

Bertha 。/ 2021年12月20日 01:13/ 0 赞/ 261 阅读