。オールオワンのデータ構造

432. All O`one Data Structure

Difficulty: Hard

Topics: Hash Table, Linked List, Design, Doubly-Linked List

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⁴ calls will be made to inc, dec, getMaxKey, and getMinKey.

Solution:

We need to implement a data structure that allows incrementing, decrementing, and retrieving keys with the minimum and maximum counts in constant time (O(1)).

Key Insights:

1. Hash Table (for String Count):
   We need a hash table (counts) that maps each string (key) to its count. This allows for O(1) access when incrementing or decrementing the count.

2. Doubly Linked List (for Counts):
   To keep track of the minimum and maximum counts, we can use a doubly linked list where each node represents a unique count. The node will store all strings with that count in a set. The linked list will help in retrieving the min and max counts in constant time by keeping track of the head (min) and tail (max) nodes.

3. Two Hash Maps:

   • A hash map (key_to_node) will map each string (key) to the node in the doubly linked list that stores its count. This allows us to move the key from one count node to another in O(1) time when we increment or decrement the count.
   • Another hash map (counts) will map each count to its corresponding node in the doubly linked list, ensuring we can locate the node for any count in O(1) time.

Plan:

• inc(key):

  • If the key exists, increase its count by 1 and move it to the next node (create a new node if necessary).
  • If the key does not exist, create a new node with count 1 and insert it.

• dec(key):

  • Decrease the count of the key by 1.
  • If the count becomes zero, remove the key from the data structure.

• getMaxKey() and getMinKey():

  • Return the first key from the tail node (max count) or head node (min count) in constant time.

Let's implement this solution in PHP: 432. All O`one Data Structure

inc($key);
 * $obj->dec($key);
 * $ret_3 = $obj->getMaxKey();
 * $ret_4 = $obj->getMinKey();
 */

// Example usage
$allOne = new AllOne();
$allOne->inc("hello");
$allOne->inc("hello");
echo $allOne->getMaxKey(); // returns "hello"
echo $allOne->getMinKey(); // returns "hello"
$allOne->inc("leet");
echo $allOne->getMaxKey(); // returns "hello"
echo $allOne->getMinKey(); // returns "leet"
?>





  
  
  Explanation:




Data Structure:



key_to_node: Maps each key to the corresponding node in the doubly linked list.

counts: Maps each count to its corresponding node in the doubly linked list.

head and tail: Dummy head and tail nodes for easier manipulation of the doubly linked list.



Methods:


inc($key): キーが存在する場合、そのカウントをインクリメントし、リスト内の適切なノードに移動します。そうでない場合は、カウント 1 で挿入します。

dec($key): キーの数を減らし、キーを削除するか、適切なノードに移動します。

getMaxKey(): 二重リンクリストの末尾のノードからキーを返します (最大数)。

getMinKey(): 二重リンクリストの先頭のノードからキーを返します (最小カウント)。





  
  
  複雑：



すべての操作は、平均時間計算量が O(1) で実行されるように設計されています。


さらに説明が必要な場合はお知らせください。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:


LinkedIn
GitHub



          

            
  

            
        
以上が。オールオワンのデータ構造の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。