Implement a data structure supporting the following operations:
- Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
- Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
- GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
- GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".
Challenge: Perform all these in O(1) time complexity.
相关题目：380. Insert Delete GetRandom O(1); 381. Insert Delete GetRandom O(1) - Duplicates allowed
问题分析
问题的大意是说让我们设计一种key-value数据结构，使得这种数据结构的插入，删除，查询都是O(1)的时间复杂度。key是一个string，value是某一个key在数据结构中的数量。Inc(key)是插入操作，如果数据结构中没有该key，插入该key，如果有则把该key的数量加一。Dec(key)是删除操作，把该key的数量减一，如果某个key数量为0，则清除该key。GetMaxKey()是返回value(数量)最多的key，如果没有返回空字符串。GetMinKey()类似，返回数量最少的，没有则返回空。
解题思路
一看到要求是O(1)的插入删除查询，基本的思路都是哈希。换而言之，我们数据结构中至少得有一个unordered_map<string, xxx>类似的东西，来进行插入删除操作。这很容易就让人想到Leetcode 380题和381题，也是要求插入删除查找都为O(1)，而且查找是随机查找，返回一个随机值，可以使用一个哈希表+一个数组实现，其中数组是无序的。然而，现在由于有GetMaxKey()和GetMinKey()存在，这表明我们除了要有哈希的地方，还得有一个按照value(数量)排序的有序表。然而，世界上根本没有任意插入删除查询都为O(1)的完美有序表。题目的关键在于，插入和删除都只会在有序表的表未进行。因为删除操作只会在次数为1的时候进行，新插入的元素的次数也只可能是1。因此数组(似乎)满足这个要求，因为在数组尾部插入和删除元素的操作可以近似看做O(1)。那么可以设计核心的数据结构如下：
vector<pair<int,string>> values;//按照value排序的有序表 unordered_map<string,int> hashMap;//对key哈希的哈希表，表值为有序表的下标 举个栗子：对于插入"b,a,b,a,c,a,d"来说，其逻辑结构如下：
如果是查询操作，可以返回数组头或数组未的字符串值，其复杂度为O(1)。
如果是插入操作，当哈希表有存在该key的时候，对应数组下标的计数值加1，如果计数值比数组中的前一个数大，那么交换这两个元素的位置，同时交换这两个keys对应的哈希表的值(即下标值)；当不存在该key的时候，新建一个key插入到哈希表，其值对应的是数组的末尾，再把一个计数为1，字符串为该key的值插入到数组尾部，其复杂度为O(1)。
如果是删除操作，当哈希表存在这个key的时候，对应表值(下标值)的数组元素计数值减一，如果计数值比数组中的后一个值小，交换两个元素位置，同时交换两个keys对应的哈希表的值(下标值)；当计数值为0的时候这个数一定处在数组末尾，因此在哈希表中删除值，同时把数组的末尾元素去掉即可。这样(似乎)时间复杂度也是O(1)。
当在各个keys对应的次数不一样的时候，删除操作的时间复杂度肯定是常数，问题出在如果有很多次数相同的keys，这样子我们数组内的元素的并不一定能在常数次交换而达到正确的位置，举个栗子：对于插入"b,a,b,a,c,d,c,d"来说：
这时我们要执行删除b的操作，b的次数变为1，应该处于数组的末尾。但是b必须与整个数组的元素依次进行交换，才能够到达数组末尾！因此在极端情况下，比如整个数据结构里面n个key的次数相同，删除的时间复杂度是O(n)而非O(1)!
上述数据结构的缺陷在于，不能正确的处理计数值相等的keys的删除操作，原因在于对于一个次数为n的key，它的数组的下一个元素的次数不一定比n小，因此没办法进行有效的swap操作。那么一个可能的改进方法则是，我把次数相同的keys放在数组的一个元素中，这样保证了数组中前面的元素的次数一定比后面的元素的次数大。但是这引入了个新的问题：经过若干次插入删除之后，某些次数的可能没有key在里面，需要删除这个元素才能保证查询的正确性。因此我们需要一种能在常数时间内删除任意元素的线性表，所以需要把原来的数组改成双向链表。由于时间关系，直接给出改进后的数据结构如下：
list<pair<int,unordered_set<string>>> values; unordered_map<string,list<pair<unordered_set<string>,int>>::iterator> hashMap; 比如插入顺序为"a,b,c,c,d,d,e,e,e"，其逻辑结构为：
如果是查询操作，直接返回链表头/链表尾的元素set中的任意一个key即可，O(1)。
如果是插入/删除操作，在某一个元素的set中删除该key，在相邻的链表节点的set中插入该key即可，O(1)。
特殊情况1，对于多个相等次数的key，删除某一个key，也能在常数时间内完成。比如刚刚的例子中删除d，整个数据结构变为：（变化的地方用红色标出）
特殊情况2，对于删除之后的set为空，对于链表也很好解决，比如说接着上面的数据，我要删除c，整个数据结构变为：（变化的地方用红色标出）
结果分析
- 时间复杂度： 全O(1)，原因上面已经给出。
- 空间复杂度： 平均O(N)，最坏O(N^4)。根据C++ STL 官网给出的分析，
unordered_map的空间复杂度平均是线性的，最坏可能达到四次，这和他的哈希函数有关。 - 通过时间： 36ms
- 思考和改进： 进一步来说，假设我
void inc(string key)函数和void dec(string key)函数不仅仅是插入或删除一个，而是插入或删除n个，能不能实现O(1)呢？ 仔细思考一下应该是可以的，我们需要再用一个unordered_map来取代现在的链表，类似于unordered_map<string key,int times>->unordered<int times,unordered_ste<string keys>>这样一个三层哈希的结构。
主要数据结构和方法
unordered_map<string,list<pair<unordered_set<string>,int>>::iterator> hashMap:一个key为字符串，value为list指针的哈希表，用于映射key和key对应的list元素之间的关系。list<pair<int,unordered_set<string>>> values： 一个双向链表，节点值为一个pair。pair的第一个值为该节点表示的次数t，后一个值表示整个数据结构中次数为t的所有字符串(key)的集合。void inc(string key)： 插入一个key。void dec(string key)： 删除一个key。string getMaxKey()/string getMinKey()： 返回次数最多/最小的key。
Read full article from HelloKenLee-Blog
No comments:
Post a Comment