Chỉ mục Chọn ngẫu nhiên trong C ++

Giả sử chúng ta có một mảng các số nguyên có thể trùng lặp, chúng ta phải chọn chỉ mục một cách ngẫu nhiên của một số mục tiêu nhất định. Chúng ta có thể giả định rằng số đích đã cho phải tồn tại trong mảng. Vì vậy, nếu mảng giống như [1,2,3,3,3], thì hãy chọn (3), có thể trả về 2, 3, 4 một cách ngẫu nhiên.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ret:=- 1, cnt:=1
cho tôi trong phạm vi từ 0 đến kích thước của v
- nếu v [i] =target, thì
  - nếu số ngẫu nhiên mod cnt =0, thì ret =i
  - cnt:=cnt + 1
trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
      int cnt = 1;
      for(int i = 0; i < v.size(); i++){
         if(v[i] == target){
            if(rand() % cnt++ == 0) ret = i;
         }
      }
      return ret;
   }
};
main(){
   vector<int> v = {1,2,3,3,3};
   Solution ob(v);
   cout << (ob.pick(3));
}

Đầu vào

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

Đầu ra