在O(1)时间内删除或查找任意元素

本文会介绍两道比较有技巧性的算法与数据结构题，都是和随机读取元素相关的。这些问题的技巧性子阿宇如何将哈希表和数组结合起来，使得数组的删除操作时间复杂度变成O(1)。

实现随机集合

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

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

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

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

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

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

本题的难点在于两点：

**1、插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)**。

2、**getRandom** 方法返回的元素必须等概率返回随机元素，也就是说，如果集合里面有 n 个元素，每个元素被返回的概率必须是 1/n。

我们先来分析一下：对于插入，删除，查找这几个操作，哪种数据结构的时间复杂度是 O(1)？

HashSet 肯定算一个对吧。哈希集合的底层原理就是一个大数组，我们把元素通过哈希函数映射到一个索引上；如果用拉链法解决哈希冲突，那么这个索引可能连着一个链表或者红黑树。

那么请问对于这样一个标准的 HashSet，你能否在 O(1) 的时间内实现 getRandom 函数？

其实是不能的，因为根据刚才说到的底层实现，元素是被哈希函数「分散」到整个数组里面的，更别说还有拉链法等等解决哈希冲突的机制，基本做不到 O(1) 时间等概率随机获取元素。

根据上面的分析，对于 getRandom 方法，如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。

这样我们就可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。

但如果用数组存储元素的话，插入，删除的时间复杂度怎么可能是 O(1) 呢？

可以做到！对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。

所以，如果我们想在 O(1) 的时间删除数组中的某一个元素 **val**，可以先把这个元素交换到数组的尾部，然后再 pop 掉。

交换两个元素必须通过索引进行交换对吧，那么我们需要一个哈希表 m 来记录每个元素值对应的索引。

type RandomizedSet struct {
    nums []int
    m    map[int]int 
}


/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    return RandomizedSet{make([]int,0),make(map[int]int,0)}
}


/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    if _,ok := this.m[val];ok {
        return false
    }
    this.nums = append(this.nums,val) // 在数组末尾插入val
    this.m[val] = len(this.nums)-1    // 将val作为key加入到map中，其value是其在数组中的索引

    return true
}


/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    if _,ok := this.m[val];!ok {
        return false
    }
    index := this.m[val]
    this.nums[index] = this.nums[len(this.nums)-1]  // 将数组最后一个元素移动到index的位置
    this.m[this.nums[index]] = index                // 更新移动后元素在map中的value值
    delete(this.m, val)															// 删除val健值对
    this.nums = this.nums[:len(this.nums)-1]        // pop数组最后一个元素
    return true
}


/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
  	i := rand.Intn(len(this.nums))    // i取从0到len(this.nums)-1的随机数
    return this.nums[i]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */