leetcode 382 链表随机节点 蓄水池取样算法

缘起

学习 蓄水池取样 算法 leetcode 382 链表随机节点

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:

// 初始化一个单链表 [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()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

其实此题来自于《编程珠玑》

问题：如何随机从n个对象中选择一个对象，这n个对象是按序排列的，但是在此之前你是不知道n的值的。

首先，如果你事先知道n的值的话, 那么问题就可以简单的用一个大随机数rand()%n得到一个确切的随机位置，那么该位置的对象就是所求的对象，选中的概率是1/n。

但是现在tricky的地方在于我们事先不知道n的值, 通常情况下 n 非常大. 大到无法一次性把所有列表S中的对象都放到内存中（就像是蓄水池中捞针一样~ 所以本题才叫蓄水池抽样算法（reservoir sampling） ）

算法:

我们总是选择第1个对象，以1/2的概率选择第2个(如果选中的话, 则选中的第二个将覆盖掉第一个成为可能最终返回给调用者的对象，后面同理)，以1/3的概率选择第3个，以此类推，即以1/m的概率选择第m个对象。当该过程结束时（即执行n次, 注意, 这和我们事先知道n的大小是不同的, 因为即便我们无法一次将n个对象加载到内存中, 但是我们依旧可以执行完整根链表），每一个对象具有相同的选中概率，即1/n，证明如下（其实就是高中数学）

1
第m个对象最终被选中的概率P=选择m的概率*其后面所有对象不被选择的概率，

这就是蓄水池抽样算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    Solution(ListNode* head) 
	{
		srand((int)(time(0)));
		this->dummy = this->head = head;
    }
    
    int getRandom()
	{
		this->dummy = this->head;
		int cnt = 0, ans = head->val;
		while(dummy)
		{
			ListNode *cur = head;
			int x = randint(cnt++); // 随机返回一个 [0,cnt]中的整数x
			while(x--) // 走x步就是此次选择的对象
			{
				cur = cur->next;
			}
			ans = cur->val;
			dummy = dummy->next;
		}
		return ans;
    }

	int randint(int i) // 随机生成[0,i]中的一个整数
	{
		return rand()%(i+1);
	}

private:
	ListNode *head, *dummy;
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
500 ms
, 在所有 cpp 提交中击败了
7.50%
的用户
内存消耗 :
16.3 MB
, 在所有 cpp 提交中击败了
65.28%
的用户