ধরুন আমাদের একটি এককভাবে লিঙ্ক করা তালিকা আছে, আমাদের লিঙ্ক করা তালিকা থেকে একটি র্যান্ডম নোডের মান খুঁজে বের করতে হবে। এখানে প্রতিটি নোডের নির্বাচিত হওয়ার একই সম্ভাবনা থাকতে হবে। সুতরাং উদাহরণস্বরূপ, যদি তালিকাটি [1,2,3] হয়, তাহলে এটি 1, 2, এবং 3 রেঞ্জে র্যান্ডম নোড ফেরত দিতে পারে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
getRandom() পদ্ধতিতে, নিম্নলিখিতগুলি করুন -
-
ret :=-1, len :=1, v :=x
-
যখন v শূন্য হয় না
-
যদি rand() len দ্বারা বিভাজ্য হয়, তাহলে ret :=v এর val
-
লেন 1 দ্বারা বাড়ান
-
v :=v
এর পরের
-
-
রিটার্ন রিটার্ন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class Solution {
public:
ListNode* x;
Solution(ListNode* head) {
srand(time(NULL));
x = head;
}
int getRandom() {
int ret = -1;
int len = 1;
ListNode* v = x;
while(v){
if(rand() % len == 0){
ret = v->val;
}
len++;
v = v->next;
}
return ret;
}
};
main(){
vector<int> v = {1,7,4,9,2,5};
ListNode *head = make_list(v);
Solution ob(head);
cout << (ob.getRandom());
} ইনপুট
Initialize list with [1,7,4,9,2,5] Call getRandom() to get random nodes
আউটপুট
4 9 1
