[JAVA] Reservoir sampling / T : O(N), S : O(1)


  • 0
    J
    class Solution {
        ListNode head;
        Random rand;
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        public Solution(ListNode head) {
            this.head = head;
            this.rand = new Random();
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode cur = head; 
            ListNode chosen = cur;
            int count = 1;
            while(cur != null){
                int num = rand.nextInt(count) + 1;
                if(num == 1){
                    chosen = cur;
                }
                count++;
                cur = cur.next;
            }
            return chosen.val;
        }
    }
    

Log in to reply
 

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