LeetCode题解|380. Insert Delete GetRandom O(1)

题目链接：380. Insert Delete GetRandom O(1)

概述

这个题目要求设计一个数据结构，使得能够在O(1)时间内完成插入、删除、随机获取。

思路

看到这个要求，很自然就想到了数组。但是单纯数组并不能满足题目中要求的如果存在值才可删除/不可插入，为此，可以引入一个Map，用于保存数组中值的位置情况。

插入时，先在map中查找下是否存在val，若存在，则按题目要求，返回false，否则在数组尾部插入该值，并且在map中记录其位置。

删除时，同样是去map中查找下是否存在val，若不存在，也是按题目要求，返回false，否则的话，将数组最后一个元素last放到val的位置上，同时更新last在map中的索引，最后将数组最后一个元素删除掉。

实现

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function() {
    this.set = [];
    this.map = {};
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(val in this.map){
        return false;
    }
    this.set.push(val);
    this.map[val] = this.set.length - 1;
    return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(!(val in this.map)){
        return false;
    }
    let last = this.set.pop();
    let index = this.map[val];
    delete this.map[val];
    if(val !== last){
        this.set[index] = last;
        this.map[last] = index;
    } 
    return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    let rand = Math.floor(Math.random() * this.set.length);
    return this.set[rand]
};

/** 
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

题解合集