天天看点

Leetcode: Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();      

Solution 1: Reservior sampling: (wiki introduction)

Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn't fit into main memory.

example: size = 1

Suppose we see a sequence of items, one at a time. We want to keep a single item in memory, and we want it to be selected at random from the sequence. If we know the total number of items (n), then the solution is easy: select an index i between 1 and n with equal probability, and keep the i-th element. The problem is that we do not always know n in advance. A possible solution is the following:

  • Keep the first item in memory.
  • When the i-th item arrives (for i>1):
    • with probability 1/i, keep the new item (discard the old one)
    • with probability 1-1/i, keep the old item (ignore the new one)

So:

  • when there is only one item, it is kept with probability 1;
  • when there are 2 items, each of them is kept with probability 1/2;
  • when there are 3 items, the third item is kept with probability 1/3, and each of the previous 2 items is also kept with probability (1/2)(1-1/3) = (1/2)(2/3) = 1/3;
  • by induction, it is easy to prove that when there are n items, each item is kept with probability 1/n.
1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     ListNode start;
11 
12     /** @param head The linked list's head.
13         Note that the head is guaranteed to be not null, so it contains at least one node. */
14     public Solution(ListNode head) {
15         this.start = head;
16     }
17     
18     /** Returns a random node's value. */
19     public int getRandom() {
20         Random random = new Random();
21         ListNode cur = start;
22         int val = start.val;
23         
24         for (int i=1; cur!=null; i++) {
25             if (random.nextInt(i) == 0) {
26                 val = cur.val;
27             }
28             cur = cur.next;
29         }
30         return val;
31     }
32 }
33 
34 /**
35  * Your Solution object will be instantiated and called as such:
36  * Solution obj = new Solution(head);
37  * int param_1 = obj.getRandom();
38  */      

PROBLEM:

  • Choose 

    k

     entries from 

    n

     numbers. Make sure each number is selected with the probability of 

    k/n

BASIC IDEA:

  • 1, 2, 3, ..., k

     first and put them into the reservoir.
  • For 

    k+1

    , pick it with a probability of 

    k/(k+1)

    , and randomly replace a number in the reservoir.
  • k+i

    k/(k+i)

  • Repeat until 

    k+i

     reaches 

    n

PROOF:

  • k+i

    , the probability that it is selected and will replace a number in the reservoir is 

    k/(k+i)

  • For a number in the reservoir before (let's say 

    X

    ), the probability that it keeps staying in the reservoir is
    • P(X was in the reservoir last time)

       × 

      P(X is not replaced by k+i)

    • P(X was in the reservoir last time)

       × (

      1

       - 

      P(k+i is selected and replaces X)

      )
    • k/(k+i-1)

       × (

      1

      k/(k+i)

      1/k

    • k/(k+i)

  • When 

    k+i

    n

    , the probability of each number staying in the reservoir is 

    k/n

EXAMPLE

  • 3

     numbers from 

    [111, 222, 333, 444]

    . Make sure each number is selected with a probability of 

    3/4

  • First, choose 

    [111, 222, 333]

     as the initial reservior
  • Then choose 

    444

     with a probability of 

    3/4

  • 111

    , it stays with a probability of
    • P(444 is not selected)

       + 

      P(444 is selected but it replaces 222 or 333)

    • 1/4

      3/4

      *

      2/3

    • 3/4

  • The same case with 

    222

     and 

    333

  • Now all the numbers have the probability of 

    3/4

     to be picked