Python solution: Algorithm R in a special case (k = 1)


  • 0
    W

    Standard Algorithm R in a special case (k = 1).
    Ref: https://en.wikipedia.org/wiki/Reservoir_sampling

    from random import randint
    
    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
            """
            r, node, cnt = self.head.val, self.head.next, 1
            while node:
                cnt += 1
                if randint(1,cnt) <= 1:
                    r = node.val
                node = node.next
            return r
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(head)
    # param_1 = obj.getRandom()
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.