ดัชนีสุ่มเลือกใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่มีความเป็นไปได้ที่ซ้ำกัน เราต้องสุ่มเลือกดัชนีของหมายเลขเป้าหมายที่กำหนด เราสามารถสรุปได้ว่าหมายเลขเป้าหมายที่กำหนดต้องมีอยู่ในอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นเหมือน [1,2,3,3,3] ให้เลือก (3) อาจส่งคืน 2, 3, 4 แบบสุ่ม

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

ret :=- 1, cnt :=1
สำหรับผมอยู่ในช่วง 0 ถึงขนาดของ v
- ถ้า v[i] =เป้าหมาย แล้ว
  - ถ้า mod สุ่มตัวเลข cnt =0 แล้ว ret =i
  - cnt :=cnt + 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;
      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));
}

อินพุต

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

ผลลัพธ์