力扣382链表随机节点笔记

力扣382链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

    Solution(ListNode head) 使用整数数组初始化对象。
    int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]

解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-random-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

要在链表中随机抽样并且每个元素被返回的概率相等，就不能是简单的运用随机数，看了许久没有思路，在参考官方题解后，得知一种我比较好理解的方法，既然不能直接运用随机数，那么可以先转换为能直接用随机数的数组来存储其中的数据，这样每个元素的概率是相同的，就不用担心概率问题，直接抽样即可得到结果。

class Solution {
    List<Integer> list;//定义一个integer类型的list（节点必定是整数，这里直接用integer类型）
    Random random;//定义一个random的随机数

    public Solution(ListNode head) {
        list = new ArrayList<Integer>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }//在list中依次添加传入链表节点的值，
        random = new Random();
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
        //获取list元素个数之内的随机数并作为list的索引来获得随机产生的元素
    }
}

第二种官方水塘抽样方法我比较难理解，涉及空间复杂度和数学逻辑。

需要花费 O(n) 的空间存储链表中的所有元素，那么能否做到 O(1)的空间复杂度呢？

从链表头开始，遍历整个链表，对遍历到的第 i 个节点，随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将答案置为该节点值，否则答案不变。

该算法会保证每个节点的值成为最后被返回的值的概率均为 1/n，证明如下：

在区间[0,i)内选0，即有1/i的可能性选中，其实也就相当于每个节点的概率相等了，是换了一种思路解决，官方代码：

class Solution {
    ListNode head;
    Random random;

    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }

    public int getRandom() {
        int i = 1, ans = 0;
        for (ListNode node = head; node != null; node = node.next) {
            if (random.nextInt(i) == 0) { // 1/i 的概率选中（替换为答案）
                ans = node.val;
            }
            ++i;
            //有几个节点就有几个i
        }
        return ans;
    }
}