Problem
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.
Use DoublyLinkedList to get max/min key (max/min count) We put max count Bucket at tail, min count Bucket at head, O(1) So the node(Bucket) must contain count property And we can use mapSolutionto access each node in O(1) Each Bucket could have multiple keys of same count, so use Set to store keys To get count of a key, use Map to achieve O(1)
class AllOne { private class Bucket { int count; SetkeySet; Bucket prev; Bucket next; public Bucket(int count) { this.count = count; this.keySet = new HashSet<>(); } } private Bucket head; private Bucket tail; private Map countBucketMap; private Map keyCountMap; public AllOne() { head = new Bucket(Integer.MIN_VALUE); tail = new Bucket(Integer.MAX_VALUE); head.next = tail; tail.prev = head; countBucketMap = new HashMap<>(); keyCountMap = new HashMap<>(); } public void inc(String key) { if (keyCountMap.containsKey(key)) { //existing key updateKey(key, 1); } else { //new key keyCountMap.put(key, 1); if (head.next.count != 1) { addBucketAfter(head, new Bucket(1)); } head.next.keySet.add(key); countBucketMap.put(1, head.next); } } public void dec(String key) { if (keyCountMap.containsKey(key)) { int count = keyCountMap.get(key); if (count == 1) { keyCountMap.remove(key); removeKeyFromBucket(countBucketMap.get(count), key); } else { updateKey(key, -1); } } } private void updateKey(String key, int i) { int count = keyCountMap.get(key); keyCountMap.put(key, count+i); Bucket pre = countBucketMap.get(count); Bucket cur; if (countBucketMap.containsKey(count+i)) { cur = countBucketMap.get(count+i); } else { cur = new Bucket(count+i); countBucketMap.put(count+i, cur); if (i == 1) { addBucketAfter(pre, cur); } else { addBucketAfter(pre.prev, cur); } } cur.keySet.add(key); removeKeyFromBucket(pre, key); } private void addBucketAfter(Bucket pre, Bucket cur) { Bucket next = pre.next; pre.next = cur; cur.prev = pre; cur.next = next; next.prev = cur; } private void removeKeyFromBucket(Bucket bucket, String key) { bucket.keySet.remove(key); if (bucket.keySet.size() == 0) { bucket.prev.next = bucket.next; bucket.next.prev = bucket.prev; bucket.prev = null; bucket.next = null; countBucketMap.remove(bucket.count); } } public String getMaxKey() { return tail.prev == head ? "" : (String) tail.prev.keySet.iterator().next(); } public String getMinKey() { return head.next == tail ? "" : (String) head.next.keySet.iterator().next(); } }
Reference: https://leetcode.com/problems...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72309.html
Find Median from Data Stream Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examp...
摘要:原題總結棧的利用,先進后出的作用,可以保持鏈表一類的數據的連貫操作,可以用來替代廣度搜索。每一層次可以用進棧出棧進行替代。形式的數據結構,有記憶狀態的作用。應用字符串的遍歷,廣度搜索。 原題: 211. Add and Search Word - Data structure design Design a data structure that supports the follo...
Problem Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block.Once a winnin...
摘要:最大堆存的是到目前為止較小的那一半數,最小堆存的是到目前為止較大的那一半數,這樣中位數只有可能是堆頂或者堆頂兩個數的均值。我們將新數加入堆后,要保證兩個堆的大小之差不超過。最大堆堆頂大于新數時,說明新數將處在所有數的下半部分。 Data Stream Median 最新更新:https://yanjia.me/zh/2019/02/... Median is the middle v...
Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...
閱讀 2458·2021-09-28 09:36
閱讀 3597·2021-09-22 15:41
閱讀 4388·2021-09-04 16:45
閱讀 1957·2019-08-30 15:55
閱讀 2847·2019-08-30 13:49
閱讀 825·2019-08-29 16:34
閱讀 2370·2019-08-29 12:57
閱讀 1679·2019-08-26 18:42