Chọn ngẫu nhiên với danh sách đen trong C ++

Giả sử chúng ta có một danh sách đen có tên B. Đây là danh sách các số nguyên duy nhất từ ​​phạm vi [0, N), chúng tôi phải xác định một hàm để trả về một số nguyên ngẫu nhiên thống nhất từ ​​phạm vi [0, N) mà KHÔNG thuộc phạm vi B. Chúng tôi sẽ cố gắng làm cho chức năng này được tối ưu hóa hơn bằng cách giảm random (). chức năng gọi. Giả sử mảng đầu vào giống như

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

Xác định một bản đồ

• Chúng tôi sẽ khởi tạo với N và mảng v.
• đối với initalize i:=0, khi tôi
• nếu v [i]

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

Ví dụ

#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;
}

Đầu vào

Give N = 4 and array [2]

Đầu ra

1
1
0