用Python刷LeetCode必备知识点2 - SortedDict

用Python刷LeetCode必备知识点2 - SortedDict

在刷LeetCode过程中，遇到很多题目要用hashtable, 即键-值（key-value）存储使一个对象映射到另一个对象。在c++中叫映射map，而python中叫字典dict, 全称dictionary。有时候我们不仅要用到键-值（key-value）存储，还要求键keys是有序的，在c++中有unordered_map 和ordered_map，而python中常用的字典dict中的keys并不是有序的，需要有序的就需要用到Sorted Containers模块sortedcontainers.SortedDict。

Sorted Containers是用纯Python开发的模块，可以高效(O(logn))地插入或删除一个单元并且保持是有序的。它包含SortedDict, SortedSet和SortedList，提供兼容普通的dict, set和list的API，所以用法差不多。在LeetCode下可以直接使用，如果是自己的开发环境则需要手动安装，在Linux下用如下 命令安装。

$ sudo pip install sortedcontainers 

SortedDict 是一个有序的可变的映射集合，继承了dict来存储键-值并且维持keys是有序，也因此要求key是可哈希的(hashable)和可比较的(comparable)。

插入和删除 *** 作跟普通dict差不多在这里不细述。我们主要是利用其key是有序的特点，涉及的接口函数有：SortedDict.keys(), SortedDict.items()和SortedDict.values()。

以下用一个例子来说明其用法

# 导入模块库
from sortedcontainers import SortedDict

# 初始化
sorted_dict = SortedDict({1 :'a', 4 :'d', 2:'b'})

# 打印整个sorted-list
print('sorted dict is: ', sorted_dict)

# 增加一个元素
sorted_dict[3] = 'c'

# 再次打印整个sorted-list
print('sorted dict after adding an element: ', sorted_dict)

# 获取key list
print('get the key list', sorted_dict.keys())

# 获取最小key
print('get the min key', sorted_dict.keys()[0])

# 获取最大key
print('get the max key', sorted_dict.keys()[-1])

# 删除最大key
maxKey = sorted_dict.keys()[-1]
sorted_dict.pop(maxKey)

# 再次打印整个sorted-list
print('sorted dict after adding an element: ', sorted_dict)

# 删除所有
sorted_dict.clear()

print('sorted dict after removing all elements: ', sorted_dict)

实战练习：LeetCode 716. Max Stack - 链表（linked List）系列题27​​​​​​​