一、常用數(shù)據(jù)結(jié)構(gòu)概覽
- 數(shù)組（Array）
- 鏈表（Linked List）
- 棧（Stack）
- 隊(duì)列（Queue）
- 哈希表（Hash Table）
- 樹（Tree）
- 圖（Graph）
- 堆（Heap）
- 集合（Set）
- 字典樹（Trie）
二设易、數(shù)據(jù)結(jié)構(gòu)的詳細(xì)介紹
1. 數(shù)組（Array）
-
特點(diǎn)：
- 連續(xù)內(nèi)存分配：數(shù)組中的元素在內(nèi)存中連續(xù)存儲(chǔ)骤星。
- 固定大小：數(shù)組的大小在初始化后不能改變愿险。
- 快速訪問：可以通過索引快速訪問元素奄妨，時(shí)間復(fù)雜度為 O(1)。
-
適用場(chǎng)景：
- 需要快速隨機(jī)訪問元素的場(chǎng)景操骡。
-
示例代碼：
int[] numbers = new int[5]; numbers[0] = 10; int firstNumber = numbers[0]; // O(1) 訪問
2. 鏈表（Linked List）
-
特點(diǎn)：
- 動(dòng)態(tài)大小：可以隨時(shí)增加或刪除元素致稀。
- 節(jié)點(diǎn)結(jié)構(gòu)：由節(jié)點(diǎn)組成冈闭，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用。
- 順序訪問：訪問元素需要從頭節(jié)點(diǎn)開始抖单，時(shí)間復(fù)雜度為 O(n)萎攒。
-
分類：
- 單向鏈表：每個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)遇八。
- 雙向鏈表：每個(gè)節(jié)點(diǎn)有指向前一個(gè)和后一個(gè)節(jié)點(diǎn)的引用。
-
適用場(chǎng)景：
- 需要頻繁插入和刪除元素的場(chǎng)景耍休。
-
示例代碼：
class Node { int data; Node next; Node(int data) { this.data = data; } } // 創(chuàng)建鏈表 Node head = new Node(10); head.next = new Node(20);
3. 棧（Stack）
-
特點(diǎn)：
- 后進(jìn)先出（LIFO）：最后入棧的元素最先出棧刃永。
-
常用操作：
- push：入棧，時(shí)間復(fù)雜度 O(1)羊精。
- pop：出棧斯够，時(shí)間復(fù)雜度 O(1)。
-
適用場(chǎng)景：
- 處理遞歸喧锦、表達(dá)式求值读规、瀏覽器歷史記錄等。
-
示例代碼：
Stack<Integer> stack = new Stack<>(); stack.push(10); int top = stack.pop(); // O(1)
4. 隊(duì)列（Queue）
-
特點(diǎn)：
- 先進(jìn)先出（FIFO）：最先入隊(duì)的元素最先出隊(duì)燃少。
-
常用操作：
- enqueue：入隊(duì)束亏，時(shí)間復(fù)雜度 O(1)。
- dequeue：出隊(duì)阵具，時(shí)間復(fù)雜度 O(1)碍遍。
-
適用場(chǎng)景：
- 任務(wù)調(diào)度、廣度優(yōu)先搜索等阳液。
-
示例代碼：
Queue<Integer> queue = new LinkedList<>(); queue.add(10); int first = queue.poll(); // O(1)
5. 哈希表（Hash Table）
-
特點(diǎn)：
- 鍵值對(duì)存儲(chǔ)：通過鍵（Key）訪問對(duì)應(yīng)的值（Value）怕敬。
- 快速查找：平均情況下，插入帘皿、刪除东跪、查找的時(shí)間復(fù)雜度為 O(1)。
-
適用場(chǎng)景：
- 需要快速插入矮烹、刪除越庇、查找的場(chǎng)景。
-
示例代碼：
Map<String, Integer> map = new HashMap<>(); map.put("apple", 3); int count = map.get("apple"); // O(1)
6. 樹（Tree）
-
特點(diǎn)：
- 層次結(jié)構(gòu)：由節(jié)點(diǎn)和邊組成的分層數(shù)據(jù)結(jié)構(gòu)奉狈。
-
分類：
- 二叉樹：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。
- 二叉搜索樹（BST）：左子節(jié)點(diǎn)小于父節(jié)點(diǎn)涩惑，右子節(jié)點(diǎn)大于父節(jié)點(diǎn)仁期。
- 平衡樹：如紅黑樹、AVL樹竭恬，保持樹的平衡性跛蛋。
-
適用場(chǎng)景：
- 實(shí)現(xiàn)高效的查找、排序痊硕、范圍查詢等赊级。
-
示例代碼：
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } // 創(chuàng)建二叉樹節(jié)點(diǎn) TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15);
7. 圖（Graph）
-
特點(diǎn)：
- 節(jié)點(diǎn)（頂點(diǎn)）和邊：表示物體和它們之間的關(guān)系。
-
表示方法：
- 鄰接矩陣：二維數(shù)組表示節(jié)點(diǎn)之間的連接岔绸。
- 鄰接表：每個(gè)節(jié)點(diǎn)的鄰居列表理逊。
-
適用場(chǎng)景：
- 社交網(wǎng)絡(luò)橡伞、地圖導(dǎo)航、任務(wù)調(diào)度等晋被。
-
示例代碼：
// 使用鄰接表表示圖 Map<String, List<String>> graph = new HashMap<>(); graph.put("A", Arrays.asList("B", "C")); graph.put("B", Arrays.asList("A", "D"));
8. 堆（Heap）
-
特點(diǎn)：
- 完全二叉樹：所有節(jié)點(diǎn)都滿足堆的性質(zhì)兑徘。
- 大頂堆：每個(gè)父節(jié)點(diǎn)的值都大于等于其子節(jié)點(diǎn)。
- 小頂堆：每個(gè)父節(jié)點(diǎn)的值都小于等于其子節(jié)點(diǎn)羡洛。
-
適用場(chǎng)景：
- 實(shí)現(xiàn)優(yōu)先隊(duì)列挂脑、排序（堆排序）、求解 Top K 問題等欲侮。
-
示例代碼：
// 小頂堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.add(5); minHeap.add(2); int smallest = minHeap.poll(); // 2
9. 集合（Set）
-
特點(diǎn)：
- 元素唯一性：不包含重復(fù)元素崭闲。
-
適用場(chǎng)景：
- 去重操作、集合運(yùn)算（交集威蕉、并集刁俭、差集）等。
-
示例代碼：
Set<String> set = new HashSet<>(); set.add("apple"); set.add("banana"); boolean exists = set.contains("apple"); // true
10. 字典樹（Trie）
-
特點(diǎn)：
- 前綴樹：用于高效地存儲(chǔ)和檢索字符串集合忘伞，尤其是字符串前綴共享的集合薄翅。
-
適用場(chǎng)景：
- 自動(dòng)補(bǔ)全、拼寫檢查氓奈、前綴查詢等翘魄。
-
示例代碼：
class TrieNode { boolean isWord; Map<Character, TrieNode> children = new HashMap<>(); TrieNode() { isWord = false; } } // 插入單詞 void insert(TrieNode root, String word) { TrieNode node = root; for (char c : word.toCharArray()) { node.children.putIfAbsent(c, new TrieNode()); node = node.children.get(c); } node.isWord = true; }
三、算法復(fù)雜度
算法復(fù)雜度用于評(píng)估算法的性能舀奶，主要分為時(shí)間復(fù)雜度和空間復(fù)雜度暑竟。
1. 時(shí)間復(fù)雜度（Time Complexity）
- 定義：算法執(zhí)行所需時(shí)間與輸入規(guī)模之間的函數(shù)關(guān)系。
常見時(shí)間復(fù)雜度類型及示例
-
O(1) - 常數(shù)時(shí)間復(fù)雜度
描述：算法的執(zhí)行時(shí)間不隨輸入規(guī)模變化育勺。
-
示例：訪問數(shù)組中的某個(gè)元素但荤。
int getFirstElement(int[] arr) { return arr[0]; // O(1) }
-
O(log n) - 對(duì)數(shù)時(shí)間復(fù)雜度
描述：算法的執(zhí)行時(shí)間隨輸入規(guī)模的對(duì)數(shù)增長(zhǎng)。
-
示例：二分查找涧至。
int binarySearch(int[] arr, int target) { int left = 0, right = arr.length -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // O(log n) } else if (arr[mid] < target) { left = mid + 1; } else { right = mid -1; } } return -1; }
-
O(n) - 線性時(shí)間復(fù)雜度
描述：算法的執(zhí)行時(shí)間與輸入規(guī)模成正比腹躁。
-
示例：遍歷數(shù)組。
int sumArray(int[] arr) { int sum = 0; for (int num : arr) { sum += num; // O(n) } return sum; }
-
O(n log n) - 線性對(duì)數(shù)時(shí)間復(fù)雜度
描述：常見于高效排序算法南蓬，如歸并排序纺非、快速排序。
-
示例：歸并排序赘方。
void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); // O(log n) mergeSort(arr, mid + 1, right); // O(log n) merge(arr, left, mid, right); // O(n) } }
-
O(n2) - 二次時(shí)間復(fù)雜度
描述：算法的執(zhí)行時(shí)間與輸入規(guī)模的平方成正比烧颖。
-
示例：冒泡排序。
void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { // O(n) for (int j = 0; j < n - i - 1; j++) { // O(n) if (arr[j] > arr[j +1]) { // 交換 int temp = arr[j]; arr[j] = arr[j +1]; arr[j +1] = temp; } } } }
時(shí)間復(fù)雜度優(yōu)先級(jí)排行（從高效到低效）
- O(1) - 常數(shù)時(shí)間
- O(log n) - 對(duì)數(shù)時(shí)間
- O(n) - 線性時(shí)間
- O(n log n) - 線性對(duì)數(shù)時(shí)間
- O(n2) - 二次時(shí)間
- O(2?) - 指數(shù)時(shí)間
- O(n!) - 階乘時(shí)間
2. 空間復(fù)雜度（Space Complexity）
- 定義：算法執(zhí)行過程中所需的額外空間與輸入規(guī)模之間的函數(shù)關(guān)系窄陡。
常見空間復(fù)雜度類型及示例
-
O(1) - 常數(shù)空間復(fù)雜度
描述：算法所需的額外空間不隨輸入規(guī)模變化炕淮。
-
示例：在原地交換兩個(gè)變量。
void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // O(1) 空間 }
-
O(n) - 線性空間復(fù)雜度
描述：算法所需的額外空間與輸入規(guī)模成正比跳夭。
-
示例：創(chuàng)建一個(gè)新數(shù)組存儲(chǔ)輸入數(shù)組的副本涂圆。
int[] copyArray(int[] arr) { int n = arr.length; int[] newArr = new int[n]; // O(n) 空間 for (int i = 0; i < n; i++) { newArr[i] = arr[i]; } return newArr; }
-
O(n2) - 二次空間復(fù)雜度
描述：算法所需的額外空間與輸入規(guī)模的平方成正比们镜。
-
示例：創(chuàng)建一個(gè)二維矩陣。
int[][] matrix = new int[n][n]; // O(n2) 空間
空間復(fù)雜度優(yōu)先級(jí)排行（從高效到低效）
- O(1) - 常數(shù)空間
- O(log n) - 對(duì)數(shù)空間（通常出現(xiàn)在遞歸調(diào)用的棾俗郏空間中）
- O(n) - 線性空間
- O(n log n)
- O(n2) - 二次空間
四憎账、復(fù)雜度優(yōu)先級(jí)總結(jié)
-
時(shí)間復(fù)雜度優(yōu)先級(jí)（從高效到低效）：
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n2)
- O(2?)
- O(n!)
-
空間復(fù)雜度優(yōu)先級(jí)（從高效到低效）：
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n2)
數(shù)據(jù)結(jié)構(gòu)：選擇合適的數(shù)據(jù)結(jié)構(gòu)對(duì)于算法的效率至關(guān)重要。先了解所有常用的數(shù)據(jù)結(jié)構(gòu)卡辰，然后深入理解其特點(diǎn)胞皱、操作和適用場(chǎng)景。
算法復(fù)雜度：時(shí)間復(fù)雜度和空間復(fù)雜度是衡量算法性能的兩個(gè)重要指標(biāo)。了解各種復(fù)雜度類型及其優(yōu)先級(jí)，有助于在開發(fā)中選擇最優(yōu)的算法和數(shù)據(jù)結(jié)構(gòu)搁凸。
