題目來源
設(shè)計一個結(jié)構(gòu)吭敢，插入碰凶，刪除以及隨機(jī)取都是平均O(1)時間。
插入刪除是O(1)，肯定得用哈希痒留，然后隨機(jī)取O(1)的話得是數(shù)組。所以得用一個哈希加一個數(shù)組蠢沿，哈希存的是值和位置的映射伸头。
代碼如下：
class RandomizedSet {
public:
/** Initialize your data structure here. */
RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if (maps.count(val) != 0)
return false;
values.emplace_back(val);
maps[val] = values.size() - 1;
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if (maps.count(val) != 0) {
maps[values[values.size() - 1]] = maps[val];
values[maps[val]] = values[values.size() - 1];
values.pop_back();
maps.erase(val);
return true;
}
else
return false;
}
/** Get a random element from the set. */
int getRandom() {
int r = rand() % maps.size();
return values[r];
}
private:
unordered_map<int, int> maps;
vector<int> values;
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* bool param_1 = obj.insert(val);
* bool param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
