Skip to content

Latest commit

 

History

History
9 lines (9 loc) · 518 Bytes

note0382.md

File metadata and controls

9 lines (9 loc) · 518 Bytes
Raw

Leetcode 382. Linked List Random Node

  • Type: Linklist, random
  • Approach:
    1. Using Reservoir Sampling method to solve the problem.
    2. For a linklist with n elements, we have 1/m possibility to choose the mth element, and (1-m)/m possibility not to choose it. Thus, for each element, it is be choosen by a possibility of 1/n.
    3. Proven: p(m) = 1/m x (m/(m+1) x (m+1)/(m+2) x ... x (n-2)/(n-1) x (n-1)/n) = 1/n.
  • Complexity:
    • Time: O(n)
    • Space: O(1)