C++의 무작위 선택 인덱스

중복 가능성이 있는 정수 배열이 있다고 가정하면 주어진 대상 번호에서 무작위로 인덱스를 선택해야 합니다. 주어진 타겟 번호가 어레이에 존재해야 한다고 가정할 수 있습니다. 따라서 배열이 [1,2,3,3,3]과 같으면 pick(3)이 2, 3, 4를 무작위로 반환할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=- 1, cnt :=1
범위 0에서 v 크기까지의 i에 대해
- 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

출력