Last Updated on 2022-02-01 by Clay
題目
Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen. Implement theSolutionclass: -Solution(ListNode head)Initializes the object with the head of the singly-linked listhead. -int getRandom()Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.
Example 1:
Input ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 3, 2, 2, 3] Explanation Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints:
- The number of nodes in the linked list will be in the range
[1, 104]. -104 <= Node.val <= 104- At most
104calls will be made togetRandom.
Follow up:
- What if the linked list is extremely large and its length is unknown to you?
- Could you solve this efficiently without using extra space?
題目給定的輸入為一組鏈結串列（linked list）的資料，而我們要做的，就是完成題目給定的 getRandom() 函式，返回隨機的一個節點的值。需要注意的是，每個節點值的返回機率應該是相同（公平）的。
解題思路
一開始我在 getRandom() 函式中，是每次都計算輸入的鏈結串列長度，再隨機取一個節點的位置，接著建立一個新的鏈結串列移動到我所選定的節點...... 也就是說至少得跑個 2n 的時間，並非好主意。
之後偶然看到了討論區的一個解法，覺得非常有意思：一開始先設定第一個節點為 i=1，接著第一個節點取值的機率為 1/1，也就是一定會取第一個節點；接著在第二個節點 i=2，第二個節點取值的機率為 1/2，也就是有一半的機率取第二個節點值......
這個想法非常有意思，我便將其紀錄了起來。
C++ 範例程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* head = NULL;
Solution(ListNode* head) {
this->head = head;
}
int getRandom() {
int i = 1;
int ans = 0;
ListNode* p = this->head;
while (p) {
if (rand() % i == 0) ans = p->val;
++i;
p = p->next;
}
return ans;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
*/