【leetcode】398 Random Pick Index

发表于 | 分类于 ，

随机返回一个数所在数组的位置


描述

给你一个数组，给你一个数字，这个数字一定在数组中，而且可能有多个，需要输出数字的所在位置，有多个的话，需要等概率随机返回一个。

样例

1
2
输入: [1,2,3,3,3],3
输出: 2 , 3 , 4 等概率返回一个

思路

ヾ(≧▽≦*)o 这种题还算中等难度? 建立一个map，用于保存数据，之后随机返回一个就好了。好吧，这样效率是不太高。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    unordered_map<int, vector<int>> m;
public:

    Solution(vector<int> nums) {
        for (int i = 0; i < nums.size(); i++) {
            m[nums[i]].push_back(i);
        }
    }

    int pick(int target) {
        static default_random_engine e(time(0));
        uniform_int_distribution<int> u(0, m[target].size()-1);
        return m[target][u(e)];
    }
};

参考

原题链接