跳至主要內容

432. 全 O(1) 的数据结构

432. 全 O(1) 的数据结构

🔴   🔖  设计 哈希表 链表 双向链表  🔗 力扣open in new window LeetCodeopen in new window

题目

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

  • AllOne() Initializes the object of the data structure.
  • inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
  • dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
  • getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
  • getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

Example 1:

Input

["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]

[[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

[null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation

AllOne allOne = new AllOne();

allOne.inc("hello");

allOne.inc("hello");

allOne.getMaxKey(); // return "hello"

allOne.getMinKey(); // return "hello"

allOne.inc("leet");

allOne.getMaxKey(); // return "hello"

allOne.getMinKey(); // return "leet"

Constraints:

  • 1 <= key.length <= 10
  • key consists of lowercase English letters.
  • It is guaranteed that for each call to dec, key is existing in the data structure.
  • At most 5 * 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey.

题目大意

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

  • AllOne() 初始化数据结构的对象。
  • inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
  • dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
  • getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
  • getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。

注意：每个函数都应当满足 O(1) 平均时间复杂度。

解题思路

这道题可以用 哈希表 + 双向链表 来解决。

  • 链表中的每个节点存储一个字符串集合 keys，和一个正整数 count，表示 keys 中的字符串均出现 count 次。注意， count 相同的字符串存储在同一个节点中。
  • 链表从头到尾的每个节点的 count 值单调递增（但不一定连续）。
  • 每个节点还需存储指向上一个节点的指针 prev 和指向下一个节点的指针 next。
  • 另外还要用一个哈希表 map 维护每个字符串当前所处的链表节点。
  1. 对于 inc 操作：

  • 当若 key 不在链表中，判断当前链表有没有 count = 1 的节点。因为链表是按照 count 升序排列的，所以只需要看头节点的 count 是否为 1；

    • 若有则共用此节点；
    • 否则新建一个 count = 1 的节点；

  • 若 key 在链表中，设 key 所在节点为 cur，判断当前链表有没有 count = cur.count + 1 的节点。同理也只需要判断 cur.next 的 count 是否等于 cur.count + 1；

    • 若有则共用此 cur.next 节点；
    • 否则新建一个 count = cur.count + 1 的节点插入到 cur 的后面；
    • 最后，将 key 从 cur.keys 中移除，若移除后 cur.keys 为空，则将 cur 从链表中移除。并更新 map 中 key 所处的节点。
  1. 对于 dec 操作：
  • 若 key 仅出现一次：将其从 map 中移除。
  • 若 key 出现不止一次，则需要判断链表中是否有 count = cur.count - 1 的节点.
    • 若有，则共用此 cur.prev 节点;
    • 否则新建一个 count = cur.count - 1 的节点；
  • 最后，将 key 从 cur.keys 中移除，若移除后 cur.keys 为空，则将 cur 从链表中移除。
  1. 对于 getMaxKey 操作:
  • 在链表不为空时，返回链表尾节点的 keys 中的任一元素;
  • 否则返回空字符串。
  1. 对于 getMinKey 操作
  • 在链表不为空时，返回链表头节点的 keys 中的任一元素;
  • 否则返回空字符串。

复杂度分析

  • 时间复杂度：所有操作均为 O(1)，这里将字符串长度视作常数。
  • 空间复杂度：O(n)，其中 n 是调用 inc 的次数。最坏情况下每次调用 inc 传入的字符串均不相同，我们需要 O(n) 大小的哈希表来存储所有字符串。

代码

class Node {
	constructor(key, count) {
		this.keys = new Set([key || '']);
		this.count = count || 0;
	}

	insert(node) {
		node.prev = this;
		node.next = this.next;
		node.prev.next = node;
		node.next.prev = node;

		return node;
	}
	remove() {
		this.next.prev = this.prev;
		this.prev.next = this.next;
	}
}
var AllOne = function () {
	this.map = new Map();
	this.root = new Node('', 0);
	this.root.next = this.root;
	this.root.prev = this.root;
};

/**
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.inc = function (key) {
	// key 在链表中
	if (this.map.has(key)) {
		let cur = this.map.get(key),
			next = cur.next;

		if (next == this.root || next.count > cur.count + 1) {
			this.map.set(key, cur.insert(new Node(key, cur.count + 1)));
		} else {
			next.keys.add(key);
			this.map.set(key, next);
		}
		cur.keys.delete(key);
		if (cur.keys.size == 0) {
			cur.remove();
		}
	}
	// key 不在链表中
	else {
		if (this.root.next === this.root || this.root.next.count > 1) {
			this.map.set(key, this.root.insert(new Node(key, 1)));
		} else {
			this.root.next.keys.add(key);
			this.map.set(key, this.root.next);
		}
	}
};

/**
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.dec = function (key) {
	const cur = this.map.get(key);
	// count 为 1 时，直接删掉
	if (cur.count == 1) {
		this.map.delete(key);
	}
	// count 大于 1 时，寻找 dec 后 key 在链表中的位置
	else {
		const prev = cur.prev;
		if (prev == this.root || prev.count < cur.count - 1) {
			this.map.set(key, prev.insert(new Node(key, cur.count - 1)));
		} else {
			prev.keys.add(key);
			this.map.set(key, prev);
		}
	}
	cur.keys.delete(key);
	if (cur.keys.size == 0) {
		cur.remove();
	}
};

/**
 * @return {string}
 */
AllOne.prototype.getMaxKey = function () {
	if (!this.root.prev) return '';
	let maxKey = '';
	for (let key of this.root.prev.keys) {
		maxKey = key;
		break;
	}
	return maxKey;
};

/**
 * @return {string}
 */
AllOne.prototype.getMinKey = function () {
	if (!this.root.next) return '';
	let minKey = '';
	for (let key of this.root.next.keys) {
		minKey = key;
		break;
	}
	return minKey;
};

/**
 * Your AllOne object will be instantiated and called as such:
 * var obj = new AllOne()
 * obj.inc(key)
 * obj.dec(key)
 * var param_3 = obj.getMaxKey()
 * var param_4 = obj.getMinKey()
 */