สุ่มเลือกด้วยบัญชีดำใน C++

สมมติว่าเรามีบัญชีดำที่เรียกว่า B นี่คือการเก็บจำนวนเต็มเฉพาะจากช่วง [0, N) เราต้องกำหนดฟังก์ชันเพื่อคืนค่าจำนวนเต็มสุ่มที่สม่ำเสมอจากช่วง [0, N) ซึ่งไม่อยู่ใน B เราจะพยายาม ทำให้ฟังก์ชันนี้ปรับให้เหมาะสมยิ่งขึ้นโดยการลด random() เรียกใช้ฟังก์ชัน สมมติว่าอาร์เรย์อินพุตเป็นแบบ

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

กำหนดหนึ่งแผนที่

• เราจะเริ่มต้นด้วย N และอาร์เรย์ v.
• สำหรับ initalize 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