Структура данных может быть построена следующим образом:
Хранить все ключи с одинаковым количеством в HashSet keys и сопровождать этот набор значением count: давайте назовем эту пару count и keys «корзиной».
Для каждого значения счетчика, для которого есть хотя бы ключ, у вас будет такая корзина,Поместите сегменты в двусвязный список bucketList и упорядочите их по количеству.
Также создайте HashMap bucketsByKey, который сопоставляет ключ с корзиной, в которой этот ключ находится в данный момент. сохранено (ключ указан в наборе keys корзины)
Операция FindMinKey проста: получить первый контейнер из bucketList, получить ключ из его keys установить (не важно, какой) и вернуть его. Аналогично для FindMaxKey.
Операция Inc(key) будет выполнять следующие шаги:
- Получить корзину, соответствующую
key из bucketsByKey - Если этот контейнер существует, удалите ключ из набора
keys. - Если этот набор становится пустым, удалите контейнер из
bucketList - Если следующий контейнер в
bucketList имеет число, равное еще одному, добавьте ключ к его наборуи обновите bucketsByKey, чтобы он ссылался на этот сегмент для этого ключа. - Если следующий блок в
bucketList имеет другое количество (или больше нет блоков), то создайте новый блок справильный счетчик и ключ и вставьте его непосредственно перед ранее найденным интервалом в bucketList - или, если следующий интервал не был найден, просто добавьте новый в конце. - Если на шаге 2 не былоДля этого ключа найден интервал, затем предположим, что его счет был равен 0, и возьмите первый интервал из
bucketList и используйте его как «следующий интервал», начиная с шага 4.
Процесс для Dec(key) аналогично, за исключением того, что когда установлено, что счетчик уже равен 1, ничего не происходит.
Вот интерактивный фрагмент на JavaScript, который вы можете запустить здесь. Он использует собственный Map для HashMap, собственный Set для HashSet и реализует двусвязный список в виде кругового, где начало / конец помечен узлом "страж" (без данных).
Вы можете нажимать кнопки Inc / Dec для выбранной вами клавиши и контролировать вывод FindMinKey и FindMaxKey, а также просто просматривать структуру данных.
class Bucket {
constructor(count) {
this.keys = new Set; // keys in this hashset all have the same count:
this.count = count; // will never change. It's the unique key identifying this bucket
this.next = this; // next bucket in a doubly linked, circular list
this.prev = this; // previous bucket in the list
}
delete() { // detach this bucket from the list it is in
this.next.prev = this.prev;
this.prev.next = this.next;
this.next = this;
this.prev = this;
}
insertBefore(node) { // inject `this` into the list that `node` is in, right before it
this.next = node;
this.prev = node.prev;
this.prev.next = this;
this.next.prev = this;
}
* nextBuckets() { // iterate all following buckets until the "sentinel" bucket is encountered
for (let bucket = this.next; bucket.count; bucket = bucket.next) {
yield bucket;
}
}
}
class MinMaxMap {
constructor() {
this.bucketsByKey = new Map; // hashmap of key -> bucket
this.bucketList = new Bucket(0); // a sentinel node of a circular doubly linked list of buckets
}
inc(key) {
this.add(key, 1);
}
dec(key) {
this.add(key, -1);
}
add(key, one) {
let nextBucket, count = 1;
let bucket = this.bucketsByKey.get(key);
if (bucket === undefined) {
nextBucket = this.bucketList.next;
} else {
count = bucket.count + one;
if (count < 1) return;
bucket.keys.delete(key);
nextBucket = one === 1 ? bucket.next : bucket.prev;
if (bucket.keys.size === 0) bucket.delete(); // remove from its list
}
if (nextBucket.count !== count) {
bucket = new Bucket(count);
bucket.insertBefore(one === 1 ? nextBucket : nextBucket.next);
} else {
bucket = nextBucket;
}
bucket.keys.add(key);
this.bucketsByKey.set(key, bucket);
}
findMaxKey() {
if (this.bucketList.prev.count === 0) return null; // the list is empty
return this.bucketList.prev.keys.values().next().value; // get any key from first bucket
}
findMinKey() {
if (this.bucketList.next.count === 0) return null; // the list is empty
return this.bucketList.next.keys.values().next().value; // get any key from last bucket
}
toString() {
return JSON.stringify(Array.from(this.bucketList.nextBuckets(), ({count, keys}) => [count, ...keys]))
}
}
// I/O handling
let inpKey = document.querySelector("input");
let [btnInc, btnDec] = document.querySelectorAll("button");
let [outData, outMin, outMax] = document.querySelectorAll("span");
let minMaxMap = new MinMaxMap;
btnInc.addEventListener("click", function () {
minMaxMap.inc(inpKey.value);
refresh();
});
btnDec.addEventListener("click", function () {
minMaxMap.dec(inpKey.value);
refresh();
});
function refresh() {
outData.textContent = minMaxMap.toString();
outMin.textContent = minMaxMap.findMinKey();
outMax.textContent = minMaxMap.findMaxKey();
}
key: <input> <button>Inc</button> <button>Dec</button><br>
data structure (linked list): <span></span><br>
findMinKey = <span></span><br>
findMaxKey = <span></span>