题目描述

Design a data structure that supports all following operations in average O(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

解题思路

这道题复杂的地方在于，用O(1)的复杂度实现插入和删除。

如果单纯用链表实现，删除的定位操作是O(n)的复杂度；而单纯用数组或者vector的进行操作，插入操作的复杂度也是O(n)。因此，在这里，就得用到哈希表。哈希表的插入和删除操作都是O(1)的复杂度。

然而，即使用了哈希表，也不能完美的解决这道题。由于哈希表无法进行随机访问，因此无法实现getRandom函数。而能够实现线性可能性随机访问的结构只有之前提到的vector或者数组。

因此，这道题中，我们需要结合哈希表和vector。

由于题目要求可能存取相同的数字，因此哈希表采用拉链的方式扩展。

在插入一个新的数字到vector中时，哈希表对应键值记录下它的下标，如果有多个下标则用拉链的方法依次存储。

而在删除时，在链表中移去对应数字的下标；在vector中，先与最后一个元素交换（如果自己是最后一个元素则不需要交换），再移掉vector的最后一个元素。这里要注意，当与最后一个元素交换时，这个元素在链表中的下标也要相应的做出改变。

时间复杂度分析

在插入操作中，插入到vector中的复杂度是O(1)；哈希表定位到对应链表的复杂度是O(1)，将下标插入到链表的操作，由于重复元素不多，因此复杂度也是O(1)。

在删除操作中，移除链表元素的复杂度和插入一致，为O(1)；交换和移除vector最后一个元素的复杂度也为O(1)。

因此，算法中任意一个操作的复杂度都是O(1)。

源码

class RandomizedCollection {

public:

/** Initialize your data structure here. */

RandomizedCollection() { }

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

bool insert(int val) {

// cout << "insert " << val << "\n----------\n";

bool isExist = nums_pos.find(val) != nums_pos.end();

int newIndex = nums.size();

nums_pos[val].push_back(newIndex);

nums.push_back(val);

//display(nums_pos);

//display(nums);

return !isExist;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

bool remove(int val) {

bool isExist = nums_pos.find(val) != nums_pos.end();

// cout << "remove " << val << "\n----------\n";

if (isExist) {

int index = nums_pos[val].back();

nums_pos[val].pop_back();

if (nums_pos[val].empty()) {

nums_pos.erase(val);

}

if (index != nums.size() -1) {

nums_pos[nums.back()].remove(nums.size() - 1);

int temp = nums.back();

nums.back() = nums[index];

nums[index] = temp;

nums_pos[temp].push_back(index);

}

nums.pop_back();

//display(nums_pos);

//display(nums);

return isExist;

} else {

return isExist;

}

}

/** Get a random element from the collection. */

int getRandom() {

return nums[rand() % nums.size()];

}

private:

vector nums;

unordered_map> nums_pos;

};