Clear solution with brief proof of probability


  • 0
    E

    Let 1/i be the probability of the i-th element as the current element, that is, the probability of this i-th element as the final element will be:

    Pr( final element = i )
    = ( 1 / i ) { i/(i+1) * (i+1)/ (i+2) * (i+2)/(i+3) * ..... *(n-1)/n }
    = ( 1 / i ) * ( i / n )
    = 1 / n

    • The { } is the probability of all the remaining elements ,which are i+1, i+2, .... , n-1, n, missing as current element.
    • Assume there are n elements in the list eventually, but we don't need aware the exact value of n.

    Which means each element has same probability as the final element.

    #Code block
    public class Solution {
    
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        private ListNode head = null;
        public Solution(ListNode head) {
            this.head = head;
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
             ListNode cur = head;
             int ret = head.val;
             int cnt = 1;
             while (cur != null) {
                 int ran = (int)(1 + Math.random()*cnt);
                 if (ran == cnt) { ret = cur.val; }
                 cnt++;
                 cur = cur.next;
             }
             
             return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.