मान लीजिए हमारे पास n_rows पंक्तियों और n_cols स्तंभों की एक बाइनरी मैट्रिक्स है। यहां सभी मान प्रारंभ में 0 हैं। हमें एक फ़ंक्शन flip() परिभाषित करना है जो समान रूप से यादृच्छिक रूप से एक 0 मान चुनता है, इसे 1 में बदलता है, और फिर उस मान की स्थिति [row.id, col.id] लौटाता है। साथ ही, हमें एक और फ़ंक्शन reset() लिखना है जो सभी मानों को वापस 0 पर सेट करता है। हमें सिस्टम के Math.random() को कॉल की संख्या को कम करने और समय और स्थान जटिलता को अनुकूलित करने का प्रयास करना होगा।
यदि हमारे पास 2x3 क्रम की मैट्रिक्स है, और हम flip को चार बार कॉल करते हैं, तो परिणाम [0,1], [1,2], [1,0], [1,1] होगा।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
holesनामक एक मैप बनाएं,- आरंभकर्ता में, निम्नलिखित करें:
- यादृच्छिक संख्या जनरेटर आरंभ करें,
n := पंक्तियों की संख्या, m := स्तंभों की संख्या, size := n * m
- यादृच्छिक संख्या जनरेटर आरंभ करें,
- flip विधि में, निम्नलिखित करें:
id := यादृच्छिक संख्या mod size, size को 1 से घटाएं, rid := id- यदि id, holes में मौजूद है, तो
id := holes[id] holes[rid] := holes[size] जब size holes में हो अन्यथा size- एक जोड़ी लौटाएं
(id / m, id mod m)
- reset विधि में, करें:
size := n x m, और holes को साफ़ करें
उदाहरण
#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();
}
};
int main(){
Solution ob(2,2);
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
}
इनपुट
कंस्ट्रक्टर को 2,2 से आरंभ करें और flip को चार बार कॉल करें
आउटपुट
[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]
