Lexi's Leetcode solutions

[phone] 单链表,只让过一次,返回随机元素

Posted on: August 20, 2013

单链表只让过一次,所以不能先把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];

 

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,234 hits
August 2013
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031  
%d bloggers like this: