Giả sử chúng ta có một danh sách được liên kết đơn lẻ, chúng ta phải tìm giá trị của một nút ngẫu nhiên từ danh sách được liên kết. Ở đây mỗi nút phải có cùng xác suất được chọn. Vì vậy, ví dụ:nếu danh sách là [1,2,3], thì nó có thể trả về nút ngẫu nhiên trong phạm vi 1, 2 và 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Trong phương thức getRandom (), hãy làm như sau -
-
ret:=-1, len:=1, v:=x
-
trong khi v không rỗng
-
nếu rand () chia hết cho len, thì ret:=val của v
-
tăng len lên 1
-
v:=tiếp theo của v
-
-
trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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());
} Đầu vào
Initialize list with [1,7,4,9,2,5] Call getRandom() to get random nodes
Đầu ra
4 9 1