Chọn chỉ mục ngẫu nhiên (Random Pick Index) trong C++

Mô tả bài toán

Cho mảng có thể có phần tử trùng. Triển khai pick(target) trả về chỉ mục ngẫu nhiên của target với xác suất đều nhau cho các vị trí chứa target.

Ví dụ: nums=[1,2,3,3,3], pick(3) → ngẫu nhiên trả về 2, 3, hoặc 4.

Giải thuật Reservoir Sampling (K = 1)

Duyệt mảng, đếm số lần gặp target (cnt). Khi gặp lần thứ cnt, chọn chỉ mục này với xác suất 1/cnt (bằng cách rand() % cnt == 0). Điều này đảm bảo mỗi vị trí có xác suất 1/total.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    vector<int> v = {1,2,3,3,3};
    Solution ob(v);
    for (int i = 0; i < 4; i++) cout << ob.pick(3) << ' '; // ví dụ: 4 3 4 2
    return 0;
}

Độ phức tạp

• Thời gian: O(n) mỗi lần gọi pick.
• Không gian: O(n) lưu mảng (có thể tối ưu bằng map vị trí nếu gọi nhiều lần).