構(gòu)造一個(gè)針對(duì)單
1 #382 2 #Runtime: 167 ms (Beats 33.87%)
3 #Memory: 17.9 MB (Beats 11.29%)
4
5 # Definition for singly-linked list.
6 # class ListNode(object):
7 # def __init__(self, val=0, next=None):
8 # self.val = val
9 # self.next = next
10 class Solution(object):
11
12 def __init__(self, head):
13 """
14 :type head: Optional[ListNode]
15 """
16 self.head = head
17
18
19 def getRandom(self):
20 """
21 :rtype: int
22 """
23 ans = self.head
24 p = self.head
25 cnt = 0
26 while p:
27 cnt += 1
28 if random.randint(1, cnt) == 1:
29 ans = p.val
30 p = p.next
31 return ans
32
33 # Your Solution object will be instantiated and called as such:
34 # obj = Solution(head)
35 # param_1 = obj.getRandom()鏈表的函數(shù)，使之每次調(diào)用可以隨機(jī)輸出其中一個(gè)值
參考了discussion的Reservoir sampling思路->https://leetcode.com/problems/linked-list-random-node/solutions/3278159/easy-solutions-in-java-python-and-c-look-at-once/