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

[Swift]LeetCode381.O(1)时间插入、删除和获取随机元素-允许重复|InsertDeleteGetRand ...

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Design a data structure that supports all following operations in averageO(1) time.

Note: Duplicate elements are allowed. 

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains. 

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

设计一个支持在平均 时间复杂度 O(1) 下, 执行以下操作的数据结构。

注意: 允许出现重复元素。

  1. insert(val):向集合中插入元素 val。
  2. remove(val):当 val 存在时,从集合中移除一个 val。
  3. getRandom:从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例:

// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();

// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);

// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);

// 向集合中插入 2 ,返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);

// getRandom 应当有 2/3 的概率返回 1 ,1/3 的概率返回 2 。
collection.getRandom();

// 从集合中删除 1 ,返回 true 。集合现在包含 [1,2] 。
collection.remove(1);

// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();

276ms
 1 class RandomizedCollection {
 2     var nums:[Int] = [Int]()
 3     var m:[Int:Set<Int>] = [Int:Set<Int>]()
 4 
 5     /** Initialize your data structure here. */
 6     init() {
 7         
 8     }
 9     
10     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
11     func insert(_ val: Int) -> Bool {
12         var set:Set<Int> = Set<Int>()
13         if m[val] == nil
14         {
15             set.insert(nums.count)
16             m[val] = set
17         }
18         else
19         {
20             m[val]!.insert(nums.count)
21         }
22         nums.append(val)
23         return m[val]!.count == 1
24     }
25     
26     /** Removes a value from the collection. Returns true if the collection contained the specified element. */
27     func remove(_ val: Int) -> Bool {
28         var set:Set<Int> = Set<Int>()
29         if m[val] != nil
30         {
31             if m[val]!.isEmpty
32             {
33                 return false
34             }
35             var idx:Int = m[val]!.first!
36             m[val]!.removeFirst()        
37         if (nums.count - 1) != idx
38         {
39             var t:Int = nums.last!
40             nums[idx] = t
41             m[t]!.remove(nums.count - 1)
42             m[t]!.insert(idx)
43         }
44             nums.removeLast()
45             return true
46         }
47         return false        
48     }
49     
50     /** Get a random element from the collection. */
51     func getRandom() -> Int {
52         return nums[Int.random(in: 1...nums.count) % nums.count]
53     
54     }
55 }
56 
57 /**
58  * Your RandomizedCollection object will be instantiated and called as such:
59  * let obj = RandomizedCollection()
60  * let ret_1: Bool = obj.insert(val)
61  * let ret_2: Bool = obj.remove(val)
62  * let ret_3: Int = obj.getRandom()
63  */
64  

280ms

 1 class RandomizedCollection {
 2     var nums: [Int]
 3     var locs: [Int: Set<Int>]
 4     /** Initialize your data structure here. */
 5     init() {
 6         nums = []
 7         locs = [:]
 8     }
 9     
10     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
11     func insert(_ val: Int) -> Bool {
12         let loc = locs[val]
13         let contains = loc != nil
14         if !contains { locs[val] = Set<Int>() }
15         locs[val]!.insert(nums.count)
16         
17         nums.append(val)
18         return !contains
19     }
20     
21     /** Removes a value from the collection. Returns true if the collection contained the specified element. */
22     func remove(_ val: Int) -> Bool {
23         guard let loc = locs[val],
24             let removeIndex = loc.first else { return false }
25         
26         // remove before adding last num in case they are the same number
27         locs[val]!.remove(removeIndex)
28         if removeIndex != nums.count - 1 {
29             // find last number and replace number we want to remove
30             let lastNum = nums.last!
31             nums[removeIndex] = lastNum
32             
33             // remove last num location and add back
34             locs[lastNum]!.remove(nums.count-1)
35             locs[lastNum]!.insert(removeIndex)
36         }
37         nums.removeLast()
38         return true
39     }
40     
41     /** Get a random element from the collection. */
42     func getRandom() -> Int {
43         let rand = Int.random(in: 0..<nums.count)
44         return nums[rand]
45     }
46 }



鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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