2022/01/07 - 382. Linked List Random Node

382. Linked List Random Node - Medium

题目描述

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.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the integer array nums.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.

Constraints:

• The number of nodes in the linked list will be in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• At most 10^4 calls will be made to getRandom.

Solution

这道题提到了随机抽取每个node概率相同，这就是典型的水塘抽样的案例。

不过我不太会这个算法，使用了额外空间，时间复杂度是O(n)，空间复杂度也是O(n)。

class Solution {

    final Random random = new Random();
    final List<Integer> list;

    public Solution(ListNode head) {
        list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

评论