Using reservoir sampling seems to be slower than just finding the list length and randomly selecting a distance from the head


  • 0
    D
    from random import randint
    class Solution(object):
        def __init__(self, head):
            self.l = 0
            self.head, node = head, head
            while node:
                self.l += 1
                node = node.next
        def getRandom(self):
            node = self.head
            for _ in xrange(randint(0, self.l-1)):
                node = node.next
            return node.val
    

    Finishes in 164 ms.

    from random import randint
    class Solution(object):
        def __init__(self, head):
            self.head = head
        def getRandom(self):
            ans, L = 0, 0
            head = self.head
            while head:
                if not randint(0,L):
                    ans = head.val
                L += 1
                head = head.next
            return ans
    

    Finishes in 392 ms.


Log in to reply
 

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