398.随机数索引

链接：398.随机数索引
难度：Medium
标签：水塘抽样、哈希表、数学、随机化
简介：给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

题解 1 - cpp

• 编辑时间：2022-04-25
• 执行用时：92ms
• 内存消耗：37.3MB
• 编程语言：cpp
• 解法介绍：排序后二分遍历。

class Solution {
   public:
    vector<int> idxs, nums;
    int n;
    Solution(vector<int> &nums) {
        srand(time(0));
        this->nums = nums;
        n = nums.size();
        for (int i = 0; i < n; i++) idxs.push_back(i);
        sort(idxs.begin(), idxs.end(),
             [&](int &i1, int &i2) -> bool { return nums[i1] < nums[i2]; });
    }
    int pick(int target) {
        int start = find1(0, n, target);
        int end = find2(start, n - 1, target);
        return idxs[random(start, end)];
    }
    int find1(int l, int r, int target) {
        int m;
        while (l < r) {
            m = (l + r) >> 1;
            if (nums[idxs[m]] >= target)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
    int find2(int l, int r, int target) {
        int m;
        while (l < r) {
            m = (l + r + 1) >> 1;
            if (nums[idxs[m]] <= target)
                l = m;
            else
                r = m - 1;
        }
        return l;
    }
    int random(int a, int b) { return rand() % (b - a + 1) + a; }
};

题解 2 - cpp

• 编辑时间：2022-04-25
• 执行用时：44ms
• 内存消耗：34.7MB
• 编程语言：cpp
• 解法介绍：水塘抽样。

class Solution {
   public:
    vector<int> nums;
    int n;
    Solution(vector<int>& nums) {
        this->nums = nums;
        n = nums.size();
        srand(time(0));
    }
    int pick(int target) {
        int cnt = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != target) continue;
            if (rand() % ++cnt == 0) {
                ans = i;
            }
        }
        return ans;
    }
};