단일 연결 목록이 있다고 가정하면 연결 목록에서 임의의 노드 값을 찾아야 합니다. 여기서 각 노드는 선택될 확률이 동일해야 합니다. 예를 들어 목록이 [1,2,3]이면 범위 1, 2, 3의 임의 노드를 반환할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
getRandom() 메소드에서 다음을 수행하십시오 -
-
ret :=-1, len :=1, v :=x
-
v가 null이 아닌 동안
-
rand()가 len으로 나눌 수 있으면 ret :=v의 val
-
len 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