C++ এ ব্ল্যাকলিস্ট সহ র্যান্ডম পিক

ধরুন আমাদের B নামক একটি ব্ল্যাকলিস্ট রয়েছে। এটি রেঞ্জ [0, N) থেকে অনন্য পূর্ণসংখ্যাগুলিকে ধারণ করছে, আমাদের পরিসর [0, N) থেকে একটি অভিন্ন র্যান্ডম পূর্ণসংখ্যা ফেরত দেওয়ার জন্য একটি ফাংশন সংজ্ঞায়িত করতে হবে যা B-তে নেই। আমরা চেষ্টা করব random() কমিয়ে এই ফাংশনটিকে আরও অপ্টিমাইজ করুন। ফাংশন কল। ধরুন ইনপুট অ্যারে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র সংজ্ঞায়িত করুন

• আমরা N এবং অ্যারে v দিয়ে আরম্ভ করব।
• ইনিটালাইজ করার জন্য i :=0, যখন i <এর আকার v, আপডেট করুন (i 1 দ্বারা বাড়ান), −
  করুন
  • যদি v[i]
• M :=N – m এর আকার
• n :=v এর আকার
• আরম্ভ করার জন্য i :=0, যখন i করুন
• যদি v[i]
• N 1 দ্বারা হ্রাস করুন
• যখন N m এ থাকে, −
  করুন
  • N 1 দ্বারা হ্রাস করুন
• m[v[i]] :=N

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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