LeetCode 380. Insert Delete GetRandom O(1) [Swift 题解]

题目

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

insert(val): Inserts an item val to the set if not already present.

remove(val): Removes an item val from the set if present.

getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

附: 原题目链接

思路

首先想到的是直接用swift 内置的Set 数据结构, 可以非常直观的写出下面的代码。

需要注意的是对于random number 的生成, LeetCode OJ 是支持Swift 4.2之后的Int.random 方法的。

class RandomizedSet {

    var set: Set<Int>
    /** Initialize your data structure here. */
    init() {
        self.set = Set<Int>()
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    func insert(_ val: Int) -> Bool {
        if set.contains(val) {
            return false
        } else {
            set.insert(val)
            return true
        }
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    func remove(_ val: Int) -> Bool {
        if set.contains(val) {
            set.remove(val)
            return true
        } else {
            return false
        }
    }

    /** Get a random element from the set. */
    func getRandom() -> Int {
        let offset = Int.random(in: 0..<set.count)

        // if older than swift 4.2
        // let offset = randomInt(min: 0, max: set.count - 1)

        let index = set.index(set.startIndex, offsetBy: offset)
        return set[index]
    }


    //before swift 4.2
    func randomInt(min: Int, max: Int) -> Int {
        return min + Int(arc4random_uniform(UInt32(max - min + 1)))
    }

}

延伸一下的话,如果没有Set 数据结构,或者说要怎么自己实现一个Set 数据结构呢? 如果要自己实现的话应该是需要一个Dictionary + 一个 Array的。

//TODO
...

chenbo

编程爱好者

Singapore