Lexi's Leetcode solutions

单链表只让过一次，所以不能先把size找出来再rand(size)。

解法：reservoir  sampling

1. 每次在curr处，假设curr的之前这段list的random element已经找到了，此时决定curr要不要把之前找到的result替换掉？在第i个node上，选中第i个node为result的概率是1/i。所以以1/i的概率用curr来替换已经找好的previous random result.
2. 这样interative的linked list往后一个个移动，直到最后一个也做完，说明result就是list所有元素都consider了的random结果。

ListNode getRandom(ListNode head) {
  int count = 1;
  ListNode result = head;
  ListNode curr = head;
  while (curr != null) {
    int rand = generateRandBetween(1, count);
    if (rand % count == 1) //this condition will happen with prob of 1/count
      result = curr;
    curr = curr.next;
    count++;
  }
  return result;
}

蓄水池抽样的原理：

从很大（不知道有多大）的水池里取k滴水。假设在i – i处已经取了k滴水了，现在决定要不要拿i来替换已有的某个k中的元素。同样，替换的概率是1/i，但是替换k中的哪一滴水呢？所以整体概率应该是(1/i) * k。

rand = generateRandBetween(1, i);
if (rand % i <= k) //should replace something in result with arr[i]
   result[rand%i] = arr[i];