[Python] list, set, dict, collections (deque, defaultdict, Counter)
- 2021.12.23
- collections Counter defaultdict deque dict frozenset list Python Queue set
list
常用操作
| Operation | Syntax | ATC |
| Append an item x to the last | lst.append(x) | O(1) |
| Remove and return the last (most left) item in the list | lst.pop() | O(1) |
| Remove and return the ith item in the list | lst.pop(i) | O(n) |
|
|
O(n) | |
| Get Slice | lst = lst[i:j+1] | O(j – i + 1) |
| lst = lst_a + lst_b | O(na + nb) | |
| lst += lst_b | O(nb) |
lst.insert(i, x)
lst = lst.insert(i, x)註：ATC: Average Time Complexity1https://wiki.python.org/moin/TimeComplexity
扁平化 Flattern
2D → 1D
list(itertools.chain.from_iterable(2d_lst))
collections.deque
常用操作
| Operation | Syntax | ATC |
| New deque | queue = collections.deque() queue = collections.deque([e1, e2, …]) |
|
| Append from right / left | queue.append() / queue.appendleft() | O(1) |
| Pop from right / left | queue.pop() / queue.popleft() | O(1) |
| Random access in deque | queue[i] | O(n) |
|
插入 x 至位置 i 若 i >= len(queue) |
queue.insert(i, x) | |
| queue.remove(x) | ||
| del queue[i] |
註：ATC: Average Time Complexity
和 list 的對照
| list | deque | |||
| 刪掉第 index 個元素 | lst.pop(index) | del queue[index] | ||
在 Python 中實作 Queue 可使用 deque
Template
queue = collections.deque(...) while queue: cur = queue.popleft() // ... queue.append(...)
set
常用操作
| Operation | Syntax | ATC |
| Add | set_a.add(x) | O(1) |
| Contain | x in set_a | O(1) |
| set_a ⊆ set_b | set_a.issubset(set_b) | O(A) |
| List to set | set(list_a) | O(A) |
| 聯集Union | set_a | set_b | O(A + B) |
| 交集Intersection | set_a & set_b | O(min(A, B)) |
| Difference | set_a – set_b | O(A) |
| Remove element | set_a.remove(e) | O(1) |
| Randomly pop a element and remove it | set_a.pop() |
註：ATC: Average Time Complexity
空集合檢查
檢查是否為空集合
if not set_a: ...
檢查是否非空集合
if set_a: ...
set(s) ⇒ {c for c in s}, s 為 str
Nested Sets
Use frozenset()
set = {frozenset(set_a), frozenset(set_b), …}
dict
常用操作
| Operation | Syntax | ATC |
| Pop | dct.pop(x) | O(1) |
| return dct[key] if key in dct else default | dct.get(key[, default=None]) |
註：ATC: Average Time Complexity
合併字典 Merging 2 Dictionaries
dict2.update(dict1)[3]
直接修改dict2，回傳None
Time Complexity: O(1)
Space Complexity: O(1)
為什麼使用 set 和 dict
因為在 Python 中，set 和 dict 都使用了 hash table
想要查詢 x 是否於某個容器中，
相較於隨機存取（random access）的 list（O(n)），set 和 dict 更快（O(1)）
為什麼要使用 defaultdict 和 Counter取代 dict
你是否經常寫類似下列的語法：
if x not in dict_a: dict_a[x] = 0 dict_a[x] += 1
如果使用 defaultdict 和 Counter
當不存在的 key 被存取其內容時
會自動為這個新 key 對應的value初始化
（檢查某元素 e 是否在 defaultdict / Counter 並不會初始化 defaultdict[e] / Counter[e] ）
範例
Leetcode # 210. Course Schedule II
collections.defaultdict
可以指定當不存在的 key 被存取時，自動為這個新 key 對應的value初始化指定型別
例：
defaultdict_a = collections.defaultdict(list) for k, v in list_a: defaultdict_a[k].append(v)
會得到 defaultdict_a ：{'color': ['blue', 'orange', 'yellow'], 'fruit': ['banana', 'orange', 'banana']}
Nested defaultdict of defaultdict
nested_defaultdict = collections.defaultdict(lambda : collections.defaultdict(...))
collections.Counter
範例：
| Declare object | counter = collections.Counter() | |
| string to counter | counter = collections.Counter(s)
ex: |
|
|
|
counter.elements() -> iterator ex: [e for e in counter.elements()]
→ [a, a, a, a, e, b, b] |
|
|
Return a list of the n most common elements and their counts from the most common to the least (It means the list is sorted by value in descending order). If n is omitted or None, most_common() returns all elements in the counter. Elements with equal counts are ordered in the order first encountered. |
counter.most_common([n]) -> list ex: [k for k, c in counter.most_common() |
+counter/-counter 只取計數為[正/負]的元素
+counter: return {key: counter[key] for key in counter if counter[key] > 0}-counter: return {key: -counter[key] for key in counter if counter[key] < 0}
ex:
counter = Counter(a=2, b=-3, c=0)
+counter → Counter({“a”: 2})
-counter → Counter({“b”: 3})
當你需要的是出現的次數而無關順序時 ⇒ 使用 Counter 替代 list
比較倆 Counter
參考 Leetcode # 242. Valid Anagram
Refrences
Last Updated on 2024/12/20 by A1go
