मान लीजिए कि हमारे पास सकारात्मक पूर्णांकों की एक सरणी w है, w [i] इंडेक्स i के वजन का वर्णन करता है, हमें एक फ़ंक्शन पिकइंडेक्स () को परिभाषित करना होगा जो यादृच्छिक रूप से अपने वजन के अनुपात में एक इंडेक्स चुनता है।
इसलिए यदि इनपुट [1,3] जैसा है, तो पिकइंडेक्स () को पांच बार कॉल करें, तो उत्तर − 0, 1, 1, 1, 0 के रूप में आ सकता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक सरणी v परिभाषित करें,
- प्रारंभकर्ता के माध्यम से, के रूप में प्रारंभ करें
- n :=w[0]
- i के लिए 1 से लेकर w के आकार तक
- w[i] :=w[i] + w[i – 1]
- n :=w[i]
- v =w
- पिकइंडेक्स() निम्नानुसार काम करेगा -
- यादृच्छिक संख्या r लें, v का अंतिम तत्व r mod करें
- 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();
}
};
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;
} इनपुट
Initialize with [1, 3] and call pickIndex five times.
आउटपुट
1 1 1 1 0