Notes on random nodes of force buckle 382 linked list

Power button 382 Random node of linked list

I'll give you a single linked list , Randomly select a node in the linked list , And return the corresponding node value . Every node The probability of being selected is the same .

Realization Solution class ：

    Solution(ListNode head) Initializing objects with an array of integers .
    int getRandom() Randomly select a node from the linked list and return the value of the node . All nodes in the linked list have the same probability of being selected .

Example ：

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

explain
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() Method should return randomly 1、2、3 One of them , The probability of each element being returned is equal .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/linked-list-random-node
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Random sampling is required in the linked list and the probability of each element being returned is equal , You can't simply use random numbers , I haven't thought about it for a long time , After referring to the official solution , I know a method that I can understand better , Since random numbers cannot be used directly , Then it can be converted into an array of random numbers to store the data , So the probability of each element is the same , Don't worry about probability , Results can be obtained by direct sampling .

class Solution {
    List<Integer> list;// Define a integer Type of list（ Nodes must be integers , It's directly used here integer type ）
    Random random;// Define a random The random number 

    public Solution(ListNode head) {
        list = new ArrayList<Integer>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }// stay list Add the values of the incoming linked list nodes in turn ,
        random = new Random();
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
        // obtain list Random numbers within the number of elements and as list Index to get randomly generated elements 
    }
}

The second official pond sampling method is difficult for me to understand , It involves spatial complexity and mathematical logic .

Need to spend O(n) Space to store all the elements in the linked list , Can we do it O(1) The spatial complexity of ？

From the head of the chain , Traverse the entire list , On the second page traversed i Nodes , Randomly selected interval [0,i) An integer in , If it is equal to 0, Then set the answer to the node value , Otherwise, the answer remains the same .

The algorithm will ensure that the probability that the value of each node becomes the last returned value is 1/n, Prove the following ：

In the interval [0,i) Internal selection 0, That is to say 1/i The possibility of selecting , In fact, the probability of each node is equal , Is to change a way of thinking to solve , Official code ：

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  Probability selection （ Replace with the answer ）
                ans = node.val;
            }
            ++i;
            // There are just a few nodes i
        }
        return ans;
    }
}