C++에서 블랙리스트를 사용한 무작위 선택

B라는 블랙리스트가 있다고 가정합니다. 이것은 범위 [0, N)에서 고유한 정수를 저장하는 것이므로 B에 없는 범위 [0, N)에서 균일한 임의의 정수를 반환하는 함수를 정의해야 합니다. 우리는 다음을 시도할 것입니다. random()을 줄여 이 함수를 더 최적화합니다. 함수 호출. 입력 배열이 다음과 같다고 가정합니다.

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

하나의 지도 정의

• N과 배열 v로 초기화하겠습니다.
• 초기화 i의 경우:=0, i
• v[i]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int M;
   map <int,int> m;
   Solution(int N, vector<int>& v) {
      for(int i = 0; i < v.size(); i++){
         if(v[i] < N) m[v[i]] = -1;
      }
      M = N - (int)(m.size());
      int n = v.size();
      for(int i = 0; i < v.size(); i++){
         if(v[i] < M){
            while(m.count(--N));
            m[v[i]] = N;
         }
      }
   }
   int pick() {
      int x = rand() % M;
      return m.count(x)? m[x] : x;
   }
};
main(){
   vector<int> v = {2};
   Solution ob(4,v);
   cout << (ob.pick()) << endl;
   cout << (ob.pick()) << endl;
   cout << (ob.pick()) << endl;
}

입력

Give N = 4 and array [2]

출력

1
1
0