[LeetCode] 382. Linked List Random Node

崔曉明發(fā)布于2019-08-16 13:47 / 863人閱讀

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.

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

Solution

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;
    Random random;
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }
    
    /** Returns a random node"s value. */
    public int getRandom() {
        ListNode cur = head;
        int res = cur.val, count = 1;
        while (cur.next != null) {
            cur = cur.next;
            if (random.nextInt(count+1) == count) {
                res = cur.val;
            }
            count++;
        }
        return res;
    }
}

GPU云服務(wù)器云服務(wù)器 linked LeetCode LeetCode_String leetcode_35_SearchIn

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/72335.html

相關(guān)文章

leetcode382. Linked List Random Node

摘要：題目要求要求從單鏈表中，隨機(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 nodes value from the linked li...

xiaodao 2019-08-16 17:58 評(píng)論0 收藏0
LeetCode[138] Copy List with Random Pointer

LeetCode[138] Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of t...

novo 2019-08-14 15:57 評(píng)論0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大體意思就是，先復(fù)制到，順便將所有的放在再?gòu)?fù)制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結(jié)點(diǎn) Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...

Jacendfeng 2019-08-14 15:32 評(píng)論0 收藏0
[Leetcode] Copy List with Random Pointer 復(fù)制隨機(jī)指針

摘要：棧迭代復(fù)雜度時(shí)間空間如果不算新鏈表的空間則是思路由于隨機(jī)指針有可能產(chǎn)生環(huán)路，我們不能直接沿著隨機(jī)指針的方向一個(gè)一個(gè)復(fù)制。同時(shí)我們又不能沿著指針直接復(fù)制，因?yàn)槲覀儾恢离S機(jī)指針?biāo)赶虻男鹿?jié)點(diǎn)是哪個(gè)。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

Olivia 2019-08-14 12:25 評(píng)論0 收藏0
LeetCode 138：復(fù)制帶隨機(jī)指針的鏈表 Copy List with Random Poin

摘要：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對(duì)克隆列表的引用。確定隨機(jī)節(jié)點(diǎn)的關(guān)系之后再拆分鏈表。其時(shí)間復(fù)雜度為，空間復(fù)雜度為。給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。 A linked list is g...

entner 2019-08-19 10:13 評(píng)論0 收藏0