7/13 (pond sampling)

1, subject

Power button https://leetcode.cn/problems/linked-list-random-node/

2, Problem solving

class Solution {
    private int count=0;
    private ListNode head;
    private Random r =new Random();

    // Record the length of header node and linked list 
    public Solution(ListNode head) {
        this.head=head;
        while(head !=null){
            count++;
            head=head.next;
        }
        
    }
    
    // utilize Random Of nextInt() Get random integers , And find the corresponding node 
    public int getRandom() {
        ListNode node=head;
        for(int i=r.nextInt(count);i>0;i--){
            node=node.next;
        }
        return node.val;
    }
}

// Pool sampling （ Suppose there are n Number ）( For a large number of data streams of unknown length )
// Choose a number at random ： When I meet the i Element time , Should have 1/i The probability of selecting the element ,1-1/i The probability of keeping the original choice .（ Judge whether the random number is 0）
// prove ：P choice = The first i The product of the selection probability of an element and the original selection probability of its subsequent elements =1/n（ There are many options for the front elements , Not easy to calculate ）
// For example, select the first element probability ：1*P（ Since then, keep the original choice ）=1/n

// Random selection k Number ： In the i Elements are placed in k/i The probability of selecting the element , With 1-k/i Keep the original choice （ By judging whether the random number is less than k）

class Solution {
    private ListNode head;
    private Random r=new Random();

    public Solution(ListNode head) {
        this.head=head;

    }
    public int getRandom() {
        int answer=0;
        ListNode node=head;
        for(int i=0;node!=null;node=node.next){
            if(r.nextInt(i+1)==0){
                answer=node.val;
                // The first element must be selected , But whether the answer will change after that is uncertain , namely answer It must be assigned .
            }
            i++;
        }
        return answer;
    }
}

3, Run a screenshot