O(n) Time & O(1) Space Java Solution


  • 29
    A
    import java.util.*;
    public class Solution {
    
        /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
        ListNode head = null;
        Random randomGenerator = null;
        public Solution(ListNode head) {
            this.head = head;
            this.randomGenerator = new Random();
    
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode result = null;
            ListNode current = head;
            
            for(int n = 1; current!=null; n++) {
                if (randomGenerator.nextInt(n) == 0) {
                    result = current;
                }
                current = current.next;
            }
            
            return result.val;
            
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */
    

  • 0
    J

    I'm not sure whether the probabilities of getting each node are equal. Can you explain that?


  • 0
    L

    Please see Reservoir_sampling.


  • 0
    S
    This post is deleted!

  • 2
    J

    @lixx2100 Thank you.
    and this is my c++ solution rewrite from abi93k's solution

    class Solution {
        ListNode* flag;
    public:
        /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
        Solution(ListNode* head) {
            flag = head;
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            ListNode* node = flag;
            int ret = node->val;
            for(int i = 1; node; ++i) {
                if(rand() % i == 0)
                    ret = node->val;
                node = node->next;
            }
            return ret;
        }
    };
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */
    

  • 6
    W

    The probability would be equal.
    This is the basic concept like Knuth's shuffle.

    I just do not know what "its length is unknown to you" - don't we get the length once we traverse it, and a second getRandom() call would have the length known?

    Maybe it is easier to paraphrase like "its length may be varying". In this way the fixed-length solution (using extra space) won't work well any more.


  • 0
    G
    This post is deleted!

  • 1
    A

    @GOPCBR nextInt(n) chooses a random value which lies between 0 and n-1. In the first iteration, randomGenerator.nextInt(1) will return 0. Always.


  • 0
    Q

    @wei88 unknown in advance


  • 12
    D

    @jtimberlakers it looks like the probability of choosing 1st element is: 1/1 * (2-1)/2 * (3-1)/3 * (4-1)/4 * ... (N-1)/N = 1/N. And the probability of choosing i-th element is 1 * 1/i * (i+1 - 1) / (i + 1) * ... (N-1)/N = 1/N. So every element has equal probability of being chosen.

    Side note: there are many sub-cases that will reach i-th element, e.g., case 1: 1st element chosen, 2nd element not chosen, 3rd element chosen, 4th element not chosen; case 2: 1st element chosen, 2nd element chosen, 3rd element not chosen ...). No matter what, their sum is 1.


  • 0
    A

    Awesome!!! it is even probability


  • 2
    S

    @dachuan.huang Thanks! Yes, when computing i-th element's probability, we don't care whether one of the previous elements is chosen since we will set it to the result if it's chosen. So we can start from i, i is chosen and all elements after i are not chosen.


  • 1
    D

    @sometimescrazy Cool! To take a step back, I am always curious about one question: how does one get this solution?

    One way I can think of (after I know the solution..) is: we want equal probability in N elements, so let's make the probability as 1/N. The numerator is 1, and the denominator is N.

    It turns out that the numerator can come from the element itself, and the denominator can come from the last element. Then the 1/1 * 1/2 * 2/3 * .. * (N-1)/N method comes in mind..


  • 1
    W

    @dachuan-huang As long as you know Reservoir_sampling or Knuth's shuffle, the solution comes naturally.
    As to how these guys (e.g. Knuth) come up with the algorithm at the first place, well they are genius.


  • 0
    M
    This post is deleted!

  • 0
    W

    @mycoy No. The solution has nothing to do with node values. It is only working with "index": see "current = current.next".


  • 1
    C

    Can someone expand @dachuan-huang explanation please? Maths and stats are not part of my day to day life so I'm struggling a bit to grasp his/her explanation.

    I get what the Random algo does and how it works (ie you get a 'random' number between 0 and n - 1) - so I would put it this way:

    1st element -> you have 1/1 chance of getting it
    2nd element -> 1/2
    3rd element -> 1/3
    4rd element -> 1/4
    n-th element -> 1/n

    I failed to understand how he/she proved the odds are the same for all elements. Can someone clarify that to me please?


  • 2
    D

    @claudineirdj so the probability of the event "the 1st element is chosen" is actually a combination of lots of events. When the 1st element is chosen, in the 1st round, we need to choose it (1/1 probability); in the 2nd round, we cannot overwrite the existing choice, how can we guarantee that we don't overwrite the existing choice? when the random integer is not 0. The probability of the event that the random integer is not 0 is: (2-1)/2.

    The event "the 1st element is chosen" is A. Then P(A) = P(A1) * P(A2) *...*P(An) .

    A1: the 1st element is chosen in the 1st round.
    A2: the chosen element is not overwritten in the 2nd round.
    so on ...

    So that's the idea. Just a chain of multiplication.


  • 1
    I

    @abi93k This question did not say the list can be modified after creation, why not just cache its length and do nextInt() once and just get to the node. No need to iterate the whole list every time, i think.


  • 2

    If someone cannot understand, could try my explanation:
    https://discuss.leetcode.com/topic/55049/java-solution-with-cases-explain


Log in to reply
 

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