मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी w है, जहां w[i] इंडेक्स i का वजन दर्शाता है, हमें एक फ़ंक्शन pickIndex() परिभाषित करना है जो उसके वजन के अनुपात में यादृच्छिक रूप से एक इंडेक्स चुनता है।
इसलिए यदि इनपुट [1,3] है, pickIndex() को पांच बार कॉल करें, तो उत्तर आ सकता है: 0, 1, 1, 1, 0।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- एक सरणी
vपरिभाषित करें, - आरंभकर्ता के माध्यम से, निम्नानुसार आरंभ करें:
n := w[0]i = 1 से w का आकारतक:w[i] := w[i] + w[i-1]n := w[i]
v = w
pickIndex()निम्नानुसार काम करेगा:- एक यादृच्छिक संख्या r लें, r mod v के अंतिम तत्व का प्रदर्शन करें
- v से r से छोटी नहीं सबसे छोटी संख्या लें, फिर v के पहले तत्व को तत्व से घटाएं और लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int n;
vector<int> v;
Solution(vector<int>& w) {
srand(time(NULL));
n = w[0];
for(int i = 1; i < w.size(); i++){
w[i] += w[i - 1];
n = w[i];
}
v = w;
}
int pickIndex() {
return upper_bound(v.begin(), v.end(), rand() % v.back()) - v.begin();
}
};
int main(){
vector<int> v = {1,3};
Solution ob(v);
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
}
इनपुट
[1, 3] से आरंभ करें और pickIndex को पांच बार कॉल करें
आउटपुट
1 1 1 1 0