• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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  */

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift @AUTOCLOSURE 和 ?? ||发布时间:2022-07-13
下一篇:
Ubuntu下,如何安装Swift发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap