[leetcode]-Linked List Random Node

372 查看

题目描述：

给定一个单向的链表，要求以相等的概率返回

要求：

时间复杂度o（n），空间复杂度o（1）

原文描述：

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up:

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

思路分析：

因为链表的长度不固定，也没法通过下标取值，只能一边遍利，一边取值
考虑在遍历时候，动态记录长度n，然后保证当前值的返回概率是1/n，我们以第2个数为例（就是head.next.val）选取的概率为(1/2) （2/3）（3/4） ……….. (n-1) / n = 1/n （选取第2个数在长度为2的时候为1/2，其他的都不要选)而对于任意的第x数，由于可以覆盖前面的数，均有： (1/x) (x/(x+1)) *…….(n-1) / n = 1/n
第n个数就直接1/n

代码：

import java.util.Random;

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. */
    ListNode head = null;
    Random random = null;
    public Solution(ListNode head) {
        this.head = head;
        random = 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(random.nextInt(n) == 0){
                result = current;
            }
            current = current.next;
        }
        return result.val;
    }
}

我的微信号：rdst6029930

欢迎交流