leetcode382. Linked List Random Node

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

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

題目要求

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

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

思路和代碼

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

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

蓄水池算法的思路如下：

選中前K個物品放入蓄水池

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

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

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

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

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

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

證明對于前K+i個物品，每個物品被放入蓄水池中的概率為K/(K+i)，當K+i等于N時，每個物品被選中的概率為K/N

在本題中，使用蓄水池算法的N為單鏈表的長度，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;
    }