สุ่มดัชนีของตัวเลขเป้าหมายใน C++

ให้อาร์เรย์มีค่าซ้ำได้ ต้องการสุ่มดัชนีของ target โดยทุกดัชนีที่มีค่าเท่ากับ target ต้องมีโอกาสเท่ากัน (Reservoir Sampling)

ตัวอย่าง: nums=[1,2,3,3,3], pick(3) → 2, 3, หรือ 4 แบบสุ่ม

ขั้นตอนการแก้ปัญหา (Reservoir Sampling)

1. เก็บอาร์เรย์ไว้ในคลาส
2. pick(target):
   • ret = -1, cnt = 1
   • วน i = 0..n-1:
     • ถ้า :
       • ถ้า rand() % cnt == 0 → ret = i
       • cnt++
   • คืน ret

หลักการ: ตัวที่ k ที่เจอ มีโอกาส 1/k ถูกเลือก แทนที่ตัวเก่า ทำให้ทุกตัวมีโอกาสเท่ากัน 1/จำนวนทั้งหมด

ตัวอย่างโค้ด C++

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

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

int main() {
    vector<int> v = {1,2,3,3,3};
    Solution ob(v);
    cout << ob.pick(3);
}

Input

Initialize with [1,2,3,3,3] Call pick(3) to get random index positions

Output

4 3 4 2