382. Linked List Random Node

Link

Solution

這題必須確保每個node值出現的機率相等。

所以 只有一個node就是 100%出現 有2個node就是 1/2出現 有3個node就是 1/3出現 假設有n個node，只要確保第n個node出現的機率是1/n，然後n-1個node出現的機率就是 n-1 node在上一輪出線的機率 * n node在最後一輪沒出線的機率1/n-1 * n-1/n = 1/n。 以此類推第一個node出現的機率 = 1/2 * 2/3 * .....*n-1/n = 1/n。

Random random;
    ListNode h;
    public Solution(ListNode head) {
        random = new Random();
        h = head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode r = h;
        int v = r.val;
        
        for(int i = 1; r.next != null; i++){
            r = r.next;
            if(i == random.nextInt(i+1)) v = r.val;
        }
        return v;
    }