題目描述
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
解題思路
這道題復(fù)雜的地方在于，用O(1)的復(fù)雜度實(shí)現(xiàn)插入和刪除。
如果單純用鏈表實(shí)現(xiàn)，刪除的定位操作是O(n)的復(fù)雜度；而單純用數(shù)組或者vector的進(jìn)行操作，插入操作的復(fù)雜度也是O(n)。因此，在這里，就得用到哈希表。哈希表的插入和刪除操作都是O(1)的復(fù)雜度。
然而，即使用了哈希表，也不能完美的解決這道題。由于哈希表無(wú)法進(jìn)行隨機(jī)訪問(wèn)，因此無(wú)法實(shí)現(xiàn)getRandom函數(shù)。而能夠?qū)崿F(xiàn)線性可能性隨機(jī)訪問(wèn)的結(jié)構(gòu)只有之前提到的vector或者數(shù)組。
因此，這道題中，我們需要結(jié)合哈希表和vector。
由于題目要求可能存取相同的數(shù)字，因此哈希表采用拉鏈的方式擴(kuò)展。
在插入一個(gè)新的數(shù)字到vector中時(shí)，哈希表對(duì)應(yīng)鍵值記錄下它的下標(biāo)，如果有多個(gè)下標(biāo)則用拉鏈的方法依次存儲(chǔ)。
而在刪除時(shí)，在鏈表中移去對(duì)應(yīng)數(shù)字的下標(biāo)；在vector中，先與最后一個(gè)元素交換（如果自己是最后一個(gè)元素則不需要交換），再移掉vector的最后一個(gè)元素。這里要注意，當(dāng)與最后一個(gè)元素交換時(shí)，這個(gè)元素在鏈表中的下標(biāo)也要相應(yīng)的做出改變。
時(shí)間復(fù)雜度分析
在插入操作中，插入到vector中的復(fù)雜度是O(1)；哈希表定位到對(duì)應(yīng)鏈表的復(fù)雜度是O(1)，將下標(biāo)插入到鏈表的操作，由于重復(fù)元素不多，因此復(fù)雜度也是O(1)。
在刪除操作中，移除鏈表元素的復(fù)雜度和插入一致，為O(1)；交換和移除vector最后一個(gè)元素的復(fù)雜度也為O(1)。
因此，算法中任意一個(gè)操作的復(fù)雜度都是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;
};
