[Swift]LeetCode382.链表随机节点|LinkedListRandomNode

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10282841.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:

// 初始化一个单链表 [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()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

200ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 
13 class Solution {
14     var head: ListNode?
15     var current:ListNode?
16     var count = 0
17     
18     /** @param head The linked list's head.
19         Note that the head is guaranteed to be not null, so it contains at least one node. */
20     init(_ head: ListNode?) {
21         self.head = head
22         self.current = head
23         while self.current != nil {
24             count += 1
25             self.current = current?.next
26         }
27         current = head
28     }
29     
30     /** Returns a random node's value. */
31     func getRandom() -> Int {
32         var random = Int.random(in: 0 ..< count)
33         for i in 0..<random {
34             current = current?.next
35             if current == nil {
36                 current = head
37             }
38         }
39         return current!.val
40     }
41 }
42 
43 /**
44  * Your Solution object will be instantiated and called as such:
45  * let obj = Solution(head)
46  * let ret_1: Int = obj.getRandom()
47  */

356ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 
13 class Solution {
14     var head: ListNode?
15     
16     /** @param head The linked list's head.
17         Note that the head is guaranteed to be not null, so it contains at least one node. */
18     init(_ head: ListNode?) {
19         self.head = head
20     }
21     
22     /** Returns a random node's value. */
23     func getRandom() -> Int {
24         var arr: [ListNode] = []
25         var node = head
26         while node != nil {
27             arr.append(node!)
28             node = node?.next
29         }
30         let randomNum = Int.random(in: 0..<arr.count)
31         return arr[randomNum].val
32     }
33 }
34 
35 /**
36  * Your Solution object will be instantiated and called as such:
37  * let obj = Solution(head)
38  * let ret_1: Int = obj.getRandom()
39  */

416ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 
13 class Solution {
14     var head:ListNode?
15 
16     /** @param head The linked list's head.
17         Note that the head is guaranteed to be not null, so it contains at least one node. */
18     init(_ head: ListNode?) {
19         self.head = head
20     }
21     
22     /** Returns a random node's value. */
23     func getRandom() -> Int {
24         var res:Int = head!.val
25         var i:Int = 2
26         var cur:ListNode? = head?.next
27         while(cur != nil)
28         {
29             var j:Int = Int.random(in:0..<i)
30             if j == 0
31             {
32                 res = cur!.val
33             }
34             i += 1
35             cur = cur?.next
36         }
37         return res
38     }
39 }
40 
41 /**
42  * Your Solution object will be instantiated and called as such:
43  * let obj = Solution(head)
44  * let ret_1: Int = obj.getRandom()
45  */
46

468ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 
13 class Solution {
14 
15     var head: ListNode?
16     // var vals = [Int]()
17     /** @param head The linked list's head.
18         Note that the head is guaranteed to be not null, so it contains at least one node. */
19     init(_ head: ListNode?) {
20         self.head = head   
21     }
22     
23     /** Returns a random node's value. */
24     func getRandom() -> Int {
25         var curr = head
26         var count = 0
27         var result = 0
28 
29         while curr != nil {
30             count += 1
31             if Int.random(in: 0..<count) == 0 {
32                 result = curr!.val
33             }
34             curr = curr?.next
35         }
36         
37         return result
38     }
39 }
40 
41 /**
42  * Your Solution object will be instantiated and called as such:
43  * let obj = Solution(head)
44  * let ret_1: Int = obj.getRandom()
45  */