JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

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.

Example 1:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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?

Code

Reservoir sampling (水塘抽样)

当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取 k 个数据，并且要保证每个数据被抽取到的概率相等

class Solution {
    ListNode head;
    Random rand;
    public Solution(ListNode head) {
        this.head = head;
        rand = new Random();
    }

    public int getRandom() {
        ListNode temp = head;
        int selected = -1;
        int i = 1;

        while(temp != null){
            if(rand.nextFloat() < 1.0 / i){
                selected = temp.val;
            }
            temp = temp.next;
            i++;
        }

        return selected;
    }
}