215. 数组中的第K个最大元素 经典
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
第一版 优先队列，小顶堆
执行用时 :12 ms, 在所有 cpp 提交中击败了89.16%的用户
内存消耗 :9.3 MB, 在所有 cpp 提交中击败了67.49%的用户
intfindKthLargest(vector<int>&nums, intk) {
priority_queue<int, vector<int>, greater<int>>res;
for (auto&a : nums) {
res.push(a);
if (res.size() >k)
res.pop();
}
returnres.top();
}
380. 常数时间插入、删除和获取随机元素
设计一个支持在平均 时间复杂度 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();
第一版，好差的一个数字...
执行用时 :284 ms, 在所有 cpp 提交中击败了5.15%的用户
内存消耗 :121.7 MB, 在所有 cpp 提交中击败了5.07%的用户
classRandomizedSet {
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. */
boolinsert(intval) {
if (result.find(val) ==result.end())
{
result.insert({ val,val });
returntrue;
}
else
returnfalse;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
boolremove(intval) {
if (result.erase(val) ==1) returntrue;
else
returnfalse;
}
/** Get a random element from the set. */
intgetRandom() {
vector<int>temp;
temp.reserve(result.size());
for (autobeg=result.begin(); beg!=result.end(); ++beg) {
temp.push_back(beg->second);
}
intindex=rand()%temp.size();
returntemp[index];
}
private:
unordered_map<int, int>result;
};
第二版，别人的做法，很有效
执行用时 :52 ms, 在所有 cpp 提交中击败了99.49%的用户
内存消耗 :22 MB, 在所有 cpp 提交中击败了78.34%的用户
首先，要在O(1)时间内的插入删除，肯定要利用哈希表的。但是问题在于随机返回一个元素，一开始还想着直接随机一个dict.size()范围内的数，然后让一个指向dict头部的迭代器与之相加-----------仔细一想，无序容器的迭代器不支持随机访问。。。但要随机返回某个元素，肯定要用到支持随机访问得迭代器啊！
而显然，支持随机访问的迭代器必须是管理连续内存的容器，常见的有--vector 、deque、C-stying arrary
所以目前需要(1)散列表(2)支持随机访问的迭代器，所以解法是，两者都用。 这里，用vector存储每一个插入的元素，散列表dict存储插入元素的下标。这样问题的关键就不是插入了，而是删除---怎样做到O(1)时间从vector容器内删除元素呢?显然，要从vector容器内删除元素，只能从其尾部删除。所以方法是:先交换vector队尾元素和待删除元素的值(因为dict中存储了下标，所以可以直接得到待删除元素的下标)，然后把队尾元素删除，并更新原队尾元素的下标即可，其他位置的元素下标并没有变化。
classRandomizedSet {
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. */
boolinsert(intval) {
if(dict.count(val) >0)
returnfalse;
Numbers.push_back(val);
dict[val] =Numbers.size()-1;
returntrue;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
boolremove(intval) {
if(dict.count(val) ==0)
returnfalse;
dict[Numbers.back()] =dict[val]; //更新原队尾元素的下标
swap(Numbers.back(),Numbers[dict[val]]); //交换原队尾元素和待删除元素
Numbers.pop_back(); //删除原队尾元素
dict.erase(val); //删除指定元素的下标
returntrue;
}
/** Get a random element from the set. */
intgetRandom() {
intpos=Numbers.empty() ?0 :rand() %Numbers.size();
returnNumbers[pos];
}
private:
unordered_map<int, int>dict;
vector<int>Numbers
};
第三版，自己又复现一遍
执行用时 :68 ms, 在所有 cpp 提交中击败了84.10%的用户
内存消耗 :22.3 MB, 在所有 cpp 提交中击败了33.18%的用户
classRandomizedSet {
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. */
boolinsert(intval) {
if (dict.find(val) ==dict.end())//不在数组中
{
dict[val] =result.size();
result.push_back(val);
returntrue;
}
returnfalse;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
boolremove(intval) {
if (dict.find(val) !=dict.end()) {//在内存中
dict[result.back()] =dict[val];
swap(result.back(),result[dict[val]]);
dict.erase(val);
result.pop_back();
returntrue;
}
returnfalse;
}
/** Get a random element from the set. */
intgetRandom() {
intindex=result.empty() ?0 : rand() %result.size();
returnresult[index];
}
private:
unordered_map<int, int>dict;
vector<int>result;
};
