資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時裝研究
法律研究在 C++ 中連結列表隨機節點
假設我們有一個單鏈表，我們必須從連結串列中查詢一個隨機節點的值。此處每個節點被選中的機率必須相同。因此，例如，如果連結串列為 [1,2,3]，則它可以在 1、2 和 3 範圍內返回隨機節點。
為了解決此問題，我們將遵循以下步驟 −
在 getRandom() 方法中，執行以下操作 −
ret := -1, len := 1, v := x
while v 不為 null
如果 rand() 可被 len 整除，則 ret := v 的 val
將 len 增加 1
v := v 的 next
返回 ret
示例(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
更新於: 02-May-2020
320 次瀏覽
廣告