मान लीजिए हमारे पास एक ब्लैकलिस्ट B है। यह रेंज [0, N) से अद्वितीय पूर्णांकों को रखती है, हमें एक फंक्शन परिभाषित करना है जो रेंज [0, N) से एक समान यादृच्छिक पूर्णांक वापस करे जो B में न हो। हम इस फंक्शन को random() फंक्शन कॉल को कम करके अधिक अनुकूलित बनाने का प्रयास करेंगे। मान लीजिए इनपुट ऐरे इस प्रकार है -
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
एक मैप परिभाषित करें
- हम N और ऐरे v के साथ आरंभ करेंगे।
- i := 0 से प्रारंभ करें, जब i < v का आकार, i बढ़ाते हुए, करें -
- यदि v[i] < N, तो:, m[v[i]] := -1
- M := N - m का आकार
- n := v का आकार
- i := 0 से प्रारंभ करें, जब i < v का आकार, i बढ़ाते हुए, करें -
- यदि v[i] < M, तो -
- N को 1 से घटाएं
- जब N, m में है, करें -
- N को 1 से घटाएं
- m[v[i]] := N
- यदि v[i] < M, तो -
- एक फंक्शन pick() परिभाषित करें
- x := यादृच्छिक संख्या mod M
- वापस करें (यदि x, m में मौजूद है, तो m[x], अन्यथा x)
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
#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