leetcode382. Linked List Random Node

xiaodao 發(fā)布于2019-08-16 17:58 / 2328人閱讀

摘要：題目要求要求從單鏈表中，隨機(jī)返回一個(gè)節(jié)點(diǎn)的值，要求每個(gè)節(jié)點(diǎn)被選中的概率是相等的。假如一共有個(gè)物品，需要從其中挑選出個(gè)物品，要求確保個(gè)物品中每個(gè)物品都能夠被等概率選中。對(duì)于這種等概率問(wèn)題，簡(jiǎn)答的做法是通過(guò)隨機(jī)數(shù)獲取選中物品的下標(biāo)。

題目要求

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();

要求從單鏈表中，隨機(jī)返回一個(gè)節(jié)點(diǎn)的值，要求每個(gè)節(jié)點(diǎn)被選中的概率是相等的。

思路和代碼

在等概率隨機(jī)選擇算法中，最經(jīng)典的算法就是蓄水池算法。可以參考同類型題目398 random pick index。這里再次整理一下蓄水池算法的思路和簡(jiǎn)單證明。

假如一共有N個(gè)物品，需要從其中挑選出K個(gè)物品，要求確保N個(gè)物品中每個(gè)物品都能夠被等概率選中。對(duì)于這種等概率問(wèn)題，簡(jiǎn)答的做法是通過(guò)隨機(jī)數(shù)獲取選中物品的下標(biāo)。但是蓄水池算法允許我們從數(shù)據(jù)流的角度來(lái)隨機(jī)獲得K個(gè)物品，即在并不知道總體的樣本數(shù)有多少的情況下，隨機(jī)抽取K個(gè)物品。

蓄水池算法的思路如下：

選中前K個(gè)物品放入蓄水池

對(duì)于第K+1個(gè)物品，其被選中并替換蓄水池中任意一個(gè)物品的概率為K/(K+1)

對(duì)于第K+i個(gè)物品，其被選中并替換蓄水池中任意一個(gè)物品的概率為K/(K+i)

重復(fù)這個(gè)步驟直到K+i=N

對(duì)于這個(gè)算法，我們可以采用歸納法進(jìn)行簡(jiǎn)單證明。已知對(duì)于前K個(gè)物品，每個(gè)物品的被選中的概率為1，滿足了K/K=1的概率。
對(duì)于K+i-1個(gè)物品，假設(shè)每個(gè)物品被選中的概率為K/(K+i-1)。證明對(duì)于前K+i個(gè)物品，每個(gè)物品被放入蓄水池中的概率為K/(K+i)

對(duì)于第K+i個(gè)物品，其被選中并替換蓄水池中任意一個(gè)物品的概率為K/(K+i)

對(duì)于之前在蓄水池中的物品，其仍在蓄水池中的概率為之前被選中在蓄水池中概率乘以這一次未被換出蓄水池的概率，即P = P(上一輪在蓄水池中) * P(這一輪沒(méi)有被替換掉)。對(duì)此進(jìn)行計(jì)算，P(上一輪在蓄水池中) * P(這一輪沒(méi)有被替換掉) = P(上一輪在蓄水池中) * (1-P(這一輪被替換掉)) = (K / (K+i-1)) * (1 - (P * 1/K))，算出P = K/(K+i)

證明對(duì)于前K+i個(gè)物品，每個(gè)物品被放入蓄水池中的概率為K/(K+i)，當(dāng)K+i等于N時(shí)，每個(gè)物品被選中的概率為K/N

在本題中，使用蓄水池算法的N為單鏈表的長(zhǎng)度，K為1。

代碼如下：

    private ListNode head;
    private Random r;
    /** @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.r = new Random();
    }

    /** Returns a random node"s value. */
    public int getRandom() {
        ListNode tmp = this.head;
        int result = 0;
        int index = 1;
        do{
            if(r.nextInt(index) == 0) {
                result = tmp.val;
            }
            tmp = tmp.next;
            index++;
        }while(tmp != null);
        return result;
    }