import random class Solution(object): def __init__(self, head): """ @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. :type head: ListNode """ self.head = head def getRandom(self): """ Returns a random node's value. :rtype: int """ reservoir, head, pos = self.head, self.head.next, 1 while head: index = random.randint(0, pos) if index == 0: reservoir = head head = head.next pos += 1 return reservoir.val # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom()
Wish to see NP-complete problems, semaphore problems, and geometry problems as well!
1.Probability of first k items still in reservoir finally is that of never getting chosen in the process:
kth item...k+1th item......nth item
k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n
2.Probability of i'th item in reservoir finally is that of getting chosen at its round and never getting chosen later:
k/i * i/(i + 1) * ... * (n-1)/n = k/n