ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে আছে, যদি w[i] সূচক i-এর ওজন বর্ণনা করে, তাহলে আমাদের একটি ফাংশন pickIndex() সংজ্ঞায়িত করতে হবে যা এর ওজনের অনুপাতে এলোমেলোভাবে একটি সূচক বেছে নেয়।
সুতরাং যদি ইনপুটটি [1,3] এর মত হয়, তাহলে pickIndex() কে পাঁচবার কল করুন, তাহলে উত্তরটি −0, 1, 1, 1, 0 হিসাবে আসতে পারে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি অ্যারে v সংজ্ঞায়িত করুন,
- ইনিশিয়ালাইজারের মাধ্যমে, এইভাবে শুরু করুন
- n :=w[0]
- আমি রেঞ্জ 1 থেকে w
- এর আকারে
- w[i] :=w[i] + w[i – 1]
- n :=w[i]
- v =w
- pickIndex() নিচের মত কাজ করবে -
- একটি এলোমেলো সংখ্যা r নিন, v এর শেষ উপাদানটি r মোড সম্পাদন করুন
- সবচেয়ে ছোট সংখ্যাটি নিন, 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
