資料結構 - a920604a/leetcode GitHub Wiki
title: 資料結構與設計資料結構
tags:
- Linked List
- Trie
- Stack
- Queue
- hash table
categories:
- CS
- Data Structure
comments: false
contain
- Linked list
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(n) | O(n) |
| insert | O(1) begin | O(n) |
| delete | O(1) begin | O(n) |
如果是doubly linked list ，end的插入、刪除也是O(1)
vector 陣列
- 存取方法 back front vec.at(i)/vec[i] data
- 修改器 push_back pop_back insert clear erase emplace_back emplace swap
- 容量 size empty resize reserve capacity shrink_to_fit
- 疊代 begin end rbegin rend cbegin cend crbegin crend
list 雙向連結串列
- 存取方法 : back front
- 修改器 : push_front/emplace_front pop_front push_back/emplace_back pop_back insert/emplace erase clear swap
- 容量 size empty resize
- 疊代 begin end rbegin rend cbegin cend crbegin crend
- 其他操作 merge sort reverse remove/remove_if splice unique
forward_list 才是 singly-linked list
- 存取方法 : front
- 修改器 : push_front/emplace_front pop_front emplace_after insert_after erase_after swap clear
- 容量 resize empty
- 疊代 begin end rbegin rend
- 其他操作 merge sort reverse remove/remove_if splice_after unique
array
- 存取方法 : back front arr.at(i)/arr[i] data
- 容量 size empty
- 疊代 begin end rbegin rend cbegin cend crbegin crend
- 其他操作 fill swap
string 我不在container library
存取方法 str.at(i)/str[i] front back data c_str substr 容量 size empty resize reserve length capacity 修改器 push_back pop_back insert clear erase append copy replace swap + find compare 疊代 begin end rbegin rend cbegin cend crbegin crend
Queue 可以array 、 linked list實現
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(n) | O(n) |
| insert | O(1) | O(1) |
| delete | O(1) | O(1) |
- 常用方法 push pop front back size empty swap emplace
- back() front() push_back() pop_front()
priority_queue 用vector 實作 但資料結構是 max-heap
- 常用方法 push pop top size empty swap emplace
- front() push_back() pop_back()
min heap
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(n) | O(n) |
| insert | O(1) | O(logn) |
| find-min | O(1) | O(1) |
| delete-min | O(logn) | O(logn) |
deque
- 存取方法 deq.at(i)/deq[i] front back
- 容量 size empty resize max_size shrink_to_fit
- 修改器 push_back/emplace_back pop_back push_front/emplace_front pop_front insert/emplace clear erase swap
- 疊代 begin end rbegin rend cbegin cend crbegin crend
Stack
| algorithm | Average | Worst case |
|---|---|---|
| space | O(k) | O(k) |
| search | O(n) | O(n) |
| insert | O(1) | O(1) |
| delete | O(1) | O(1) |
- 常用方法 push pop top empty size swap emplace
set 紅黑樹
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(logN) | O(logN) |
| insert | O(logN) | O(logN) |
| delete | O(logN) | O(logN) |
- 容量 size empty max_size
- 修改器 insert clear erase swap emplace emplace_hint merge extract
- 疊代 begin end rbegin rend cbegin cend crbegin crend
- 查詢 count find equal_range lower_bound upper_bound contain
unordered_set hash 結構
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(1) | O(1) 分攤後 |
| insert | O(1) | O(1) 分攤後 |
| delete | O(1) | O(1) 分攤後 |
-
容量 size empty max_size
-
修改器 insert clear erase swap emplace emplace_hint merge extract
-
疊代 begin end cbegin cend
-
查詢 count find equal_range contain
-
hash方法 load_factor max_load_factor rehash reserve
-
bucket 接口 begin/cbegin end/cend bucket_count max_bucket_count bucket_size bucket
map 紅黑樹
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(logN) | O(n) |
| insert | O(logN) | O(1) |
| delete | O(logN) | O(1) |
- 存取方法 deq.at(i)/deq[i]
- 容量 size empty
- 修改器 insert clear erase swap emplace emplace_hint merge extract insert_or_assign try_emplace
- 疊代 begin end rbegin rend cbegin cend crbegin crend
- 查詢 count find equal_range lower_bound upper_bound contain
unordered_map hash 結構
| algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(1) | O(1) 分攤後 |
| insert | O(1) | O(1) 分攤後 |
| delete | O(1) | O(1) 分攤後 |
-
存取方法 deq.at(i)/deq[i]
-
容量 size empty max_size
-
修改器 insert clear erase swap emplace emplace_hint merge extract insert_or_assign try_emplace
-
疊代 begin end cbegin cend
-
查詢 count find equal_range contain
-
hash方法 load_factor max_load_factor rehash reserve
-
bucket 接口 begin/cbegin end/cend bucket_count max_bucket_count bucket_size bucket
unordered_map vs. map and unordered_set vs set
unordered ，是無序的，
map set 資料訪問順序是按照插入順序而定。
例如 map 內部結構紅黑樹來實現，保證查詢、插入、刪除都是O（logN），最壞和平均都是
unordered_set unordered_map 因為是hash template to comput hash ，所以不能拿pair tuple vector 來當key，但是map set 可以拿pair tuple vector 來當key，因為 map set 是通過操作符 < 比較大小，而pair是可以比較大小的
summary
sort
| Complexity | Best case | Average case | Worst case | Memory space | Stable |
|---|---|---|---|---|---|
| Bubble | O(N) |
O(N^2) |
O(N^2) |
1 | stable |
| Insertion | O(N) |
O(N^2) |
O(N^2) |
1 | stable |
| Selection | O(N^2) |
O(N^2) |
O(N^2) |
1 | non-stable |
| Merge | O(NlogN) |
O(NlogN) |
O(NlogN) |
O(N) |
|
| Quick | O(NlogN) |
O(NlogN) |
O(N^2) |
O(N) or O(logN) |
non-stable |
| Radix | O(KN) |
||||
| Count | O(N+K) |
O(N+K) |
O(N+K) |
O(N+K) |
|
| Bucket | O(N+K) |
O(N+K) |
O(N^2) |
O(N+K) |
stable |
| Shell | O(NlogN) |
O(N^2)~O(nlog^2 N) |
1 | non-stable | |
| Heap | O(NlogN) |
O(NlogN) |
O(NlogN) |
1 | non-stable |
Count sort 計算每個鍵值的出現次數，並用額外的陣列保存
search
- linear search
- binary search
- exponential search
- junpsearch
- Interpolation search
- FibonacciSearch
time compleity
- 陣列sum : O(n)
- 矩陣相加: O(n^2)
- 矩陣相乘: O(n^3)
- 階層運算：O(n!)
- 指數時間：O(2^n)
- big O: upper bound
- big omega: lower bound
- big theta: tight bound $1<logn<n<nlogn<n^2<n^3<2^n<n!$
int f(int n){
if(n<1) return 1;
return f(n-1) + f(n-1);
}
// O(2^N)
(N-1) + (N-2) + (N-3) + ... + 2 + 1
// O(N^2)
int sum(Node node){
if(node==nullptr) return 0;
return sum(node.left) + node.val + sum(node.right);
}
// O(N) = O(2^(logN))
int factorial(int n){
if(n<0) return -1;
else if(n==0) return 1;
else return n* factorial(n-1);
}
// O(n)
int fib(int n){
if(n<=0) return 0;
else if(n==1) return 1;
return fib(n-1) +fib(n-2);
}
// O(2^N)
// but called n times is
// O(2^(N+1)) = O(2^N)
int fib(int n , int []memo){
if(n<0) return 0;
else if(n==1) return 1;
else if(memo[n]>0) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2,memo);
return memo[n];
}
// O(n)
must-have knowledge
| Data Structures | Algorithms | Concepts |
|---|---|---|
| Linked Lists | Breadth-First Search | Bit Manipulation |
| Tree,Tries & Graphs | Depth-First Search | Memory(Stack & Heap) |
| Stack & Queues | Binary Search | Recursion |
| Heaps | Merge Sort | Dynamic Programming |
| Vectors/ArrayLists | Quick Sort | Big O Time & Space |
| Hash tables | Prefix Sum | |
| skip list |