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

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

[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.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
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) 下，执行以下操作的数据结构。

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

insert(val)：向集合中插入元素 val。
remove(val)：当 val 存在时，从集合中移除一个 val。
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 }