leetcode 随机采样

本文包括

• 382. Linked List Random Node
• 528. Random Pick with Weight
• 蓄水池抽样

382. 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();

题目地址: leetcode Linked List Random Node

题意: 给定一个链表，要求以相等的概率返回链表上的结点。

思路：

若已知链表长度len，那么直接随机一下0~len-1，然后遍历到那个结点。

如果不知道长度呢？

我们实时的计算当前遍历了多少个元素cnt，然后以 1/cnt 的概率选择 当前的元素，直到遍历完链表。

这样遍历一遍即可。

为啥是对的？

我们以第2个数为例（就是head.next.val）

选取的概率为(1/2)* （2/3）（3/4） ........... (n-1) / n = 1/n   （选取第2个数在长度为2的时候为1/2，其他的都不要选)

而对于任意的第x数，由于可以覆盖前面的数，均有：\(\frac{1}{x}\times \frac{x}{x+1} \times ... \times \frac{n-1}{n} = \frac{1}{n}\)

第n个数就直接1/n啦

大家都是1/n~

C++

class Solution {
	ListNode *head;
public:
	/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
	Solution(ListNode* head) :head(head) {}

	/** Returns a random node's value. */
	int getRandom() {
		int ans = 0;
		ListNode *p = head;
		for (int cnt = 1; p; cnt++, p = p->next) if (rand() % cnt == 0) ans = p->val;
		return ans;
	}
};

Java

import java.util.Random;
public class Solution {
    private ListNode head;
    private Random random;
    /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        this.random = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int ans = 0;
		ListNode p = head;
		for (int cnt = 1; p != null; cnt++, p = p.next) if (random.nextInt(cnt) == 0) ans = p.val;
		return ans;
    }
}

Python

注：在代码实现上，这里的cnt 比上面讲解中的cnt 少1   randint(x,y)返回的为[x,y]的闭区间。

import random
class Solution(object):
    def __init__(self, head):
        """
        @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.head = head

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        ans = cnt = 0
        head = self.head
        while head:
            if random.randint(0, cnt) == 0:
                ans = head.val
            head, cnt = head.next, cnt + 1
        return ans

 

528. Random Pick with Weight

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1. 1 <= w.length <= 10000
2. 1 <= w[i] <= 10^5
3. pickIndex will be called at most 10000 times.

Example 1:

Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

题目地址: leetcode Random Pick with Weight

题意: 给定一个数组表示下标对应的权重，要求按这个权重数组随机的抽样。（抽样的概率和权重成正比）

思路：

假设没有权重的时候给定n个数就只需要从这n个数随机抽一个即可，每个的概率是1/n。

那么有权重的时候的区别是什么呢？权重为w其实可以看成一个数重复w次，这样随机抽取，抽到的概率就是1/所有权重之和，由于一个数重复w次，因此一个数被抽到就是w/所有权重之和。

代码实现上，可以算到当前数的权重和，然后用二分查找。

Python

import random
class Solution:
    def __init__(self, w: List[int]):
        self.sum = []
        for x in w:
            if self.sum:
                self.sum.append(self.sum[-1] + x)
            else:
                self.sum.append(x)
        
    def pickIndex(self) -> int:
        if not self.sum:
            return 0
        
        L, R = 0, len(self.sum) - 1
        target = random.randint(1, self.sum[-1])
        while L < R:
            mid = (L + R) >> 1
            if target == self.sum[mid]:
                return mid
            
            if self.sum[mid] < target:
                L = mid + 1
            else:
                R = mid
        return L

 

蓄水池抽样

如果要从n个数中，等概率的抽取k个数呢？

这是蓄水池抽样算法，伪代码如下

given k;
i = 1
for num in nums:
    if i <= k:
        continue
    temp = random.randint(0, i)
    if temp < k:
        swap(nums[i], nums[temp])
    i += 1
return nums[:k]

即个数<k的时候直接放入，当做水池。

从k + 1开始，第i个数，每个数以 k / i的概率被选中，并随机的替换蓄水池的k个数中的一个，这样每个数的概率都是k / n

证明如下：

第i个数(i > k)最后被选中的概率 = 第i个数时以概率 k / i被选中，之后的数不被选中或者选中的不替换第i个数 \[ \frac{k}{i} * [(1- \frac{k}{i + 1} + \frac{k}{i + 1}\times\frac{k-1}{k}) \times (1- \frac{k}{i + 2} + \frac{k}{i + 2}\times\frac{k-1}{k})\times... \times (1- \frac{k}{n} + \frac{k}{n}\times\frac{k-1}{k})] \\= \frac{k}{i} \times (\frac{i}{i + 1} \times \frac{i + 1}{i + 2} \times ... \times \frac{n - 1}{n} ) = \frac{k}{n} \]

而对于前k个数，类似的也有 \[ (1- \frac{k}{k + 1} + \frac{k}{k + 1}\times\frac{k-1}{k}) \times (1- \frac{k}{k + 2} + \frac{k}{k + 2}\times\frac{k-1}{k})\times... \times (1- \frac{k}{n} + \frac{k}{n}\times\frac{k-1}{k}) \\= \frac{k}{k + 1} \times \frac{k + 1}{k + 2} \times ... \times \frac{n - 1}{n} = \frac{k}{n} \]

本题是leetcode 382 Linked List Random Node 的题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/