[leetcode] 398. Random Pick Index

我是链接

看到这道题，想到做的几道什么洗牌的题，感觉自己不是很熟，但也就是rand（）函数的调用，刚开始用map<int, vector<int >>来做，tle，后来就想着直接保存nums数组，和每个元素的数目，然后先生成一个随机的第几个target，然后从nums里面再找这个index，交了，就过了，有套路么？

class Solution {

public:

    map<int, int> m;

    vector<int> num;

    Solution(vector<int> nums) {

        num = nums;

        for (int i = 0; i < nums.size(); i++) {

            m[nums[i]]++;

        }

        srand( (unsigned)time( NULL ) );

    }

    int pick(int target) {

        int t = m[target];

        int index = rand() % t + 1;

        t = 0;

        for (int i = 0; i < num.size(); i++) {

            if(num[i] == target) {

                t++;

                if(t == index) {

                    return i;

                }

            }

        }

        return 0;

    }

};

巴特西

[leetcode] 398. Random Pick Index

最新文章

热门文章