मान लीजिए कि हमारे पास n_rows पंक्तियों की संख्या और n_cols स्तंभों की संख्या के साथ एक बाइनरी मैट्रिक्स है। यहां सभी मान प्रारंभ में 0 हैं। हमें एक फ़ंक्शन फ्लिप() को परिभाषित करना है जो यादृच्छिक रूप से 0 मान समान रूप से चुनता है, इसे 1 में बदलता है, और फिर उस मान की स्थिति [row.id, col.id] लौटाता है। साथ ही, हमें एक और फ़ंक्शन रीसेट() लिखना होगा जो सभी मानों को 0 पर वापस सेट करता है। हमें सिस्टम के Math.random() पर कॉल की संख्या को कम करने और समय और स्थान जटिलता को अनुकूलित करने का प्रयास करना होगा।
यदि हमारे पास क्रम 2x3 का मैट्रिक्स है, और हम फ्लिप को चार बार कॉल करते हैं, तो परिणाम [0,1], [1,2], [1,0], [1,1] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- छेद नामक नक्शा बनाएं,
- इनिशियलाइज़र में, निम्न कार्य करें
- यादृच्छिक संख्या जनरेटर प्रारंभ करें, n :=पंक्तियों की संख्या, m :=कॉलों की संख्या,
- आकार :=n * m
- फ्लिप विधि में, निम्न कार्य करें -
- id :=यादृच्छिक संख्या मॉड आकार, 1 से आकार घटाएं:=id
- यदि छिद्रों में id मौजूद है, तो id :=holes[id]
- छेद [छुटकारा] :=छेद [आकार] जब छेद में आकार अन्यथा आकार
- एक जोड़ी लौटाएं (id / m, id mod m)
- रीसेट विधि में, करें
- आकार :=n x m, और छिद्रों को साफ़ करें
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
unordered_map <int, int> holes;
int n;
int m;
int size;
Solution(int n_rows, int n_cols) {
srand(time(NULL));
n = n_rows;
m = n_cols;
size = n * m;
}
vector<int> flip() {
int id = rand() % size;
size--;
int rid = id;
if(holes.count(id)){
id = holes[id];
}
holes[rid] = holes.count(size) ? holes[size] : size;
return {id / m, id % m};
}
void reset() {
size = n * m;
holes.clear();
}
};
main(){
Solution ob(2,2);
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
} इनपुट
Initialize the constructor using 2,2 and call flip four times
आउटपुट
[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]