一、常用數(shù)據(jù)結構概覽
- 數(shù)組（Array）
- 鏈表（Linked List）
- 棧（Stack）
- 隊列（Queue）
- 哈希表（Hash Table）
- 樹（Tree）
- 圖（Graph）
- 堆（Heap）
- 集合（Set）
- 字典樹（Trie）
二、數(shù)據(jù)結構的詳細介紹
1. 數(shù)組（Array）
-
特點：
- 連續(xù)內存分配：數(shù)組中的元素在內存中連續(xù)存儲。
- 固定大小：數(shù)組的大小在初始化后不能改變。
- 快速訪問：可以通過索引快速訪問元素，時間復雜度為 O(1)。
-
適用場景：
- 需要快速隨機訪問元素的場景。
-
示例代碼：
int[] numbers = new int[5]; numbers[0] = 10; int firstNumber = numbers[0]; // O(1) 訪問
2. 鏈表（Linked List）
-
特點：
- 動態(tài)大小：可以隨時增加或刪除元素。
- 節(jié)點結構：由節(jié)點組成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的引用。
- 順序訪問：訪問元素需要從頭節(jié)點開始，時間復雜度為 O(n)。
-
分類：
- 單向鏈表：每個節(jié)點指向下一個節(jié)點。
- 雙向鏈表：每個節(jié)點有指向前一個和后一個節(jié)點的引用。
-
適用場景：
- 需要頻繁插入和刪除元素的場景。
-
示例代碼：
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）
-
特點：
- 后進先出（LIFO）：最后入棧的元素最先出棧。
-
常用操作：
- push：入棧，時間復雜度 O(1)。
- pop：出棧，時間復雜度 O(1)。
-
適用場景：
- 處理遞歸、表達式求值、瀏覽器歷史記錄等。
-
示例代碼：
Stack<Integer> stack = new Stack<>(); stack.push(10); int top = stack.pop(); // O(1)
4. 隊列（Queue）
-
特點：
- 先進先出（FIFO）：最先入隊的元素最先出隊。
-
常用操作：
- enqueue：入隊，時間復雜度 O(1)。
- dequeue：出隊，時間復雜度 O(1)。
-
適用場景：
- 任務調度、廣度優(yōu)先搜索等。
-
示例代碼：
Queue<Integer> queue = new LinkedList<>(); queue.add(10); int first = queue.poll(); // O(1)
5. 哈希表（Hash Table）
-
特點：
- 鍵值對存儲：通過鍵（Key）訪問對應的值（Value）。
- 快速查找：平均情況下，插入、刪除、查找的時間復雜度為 O(1)。
-
適用場景：
- 需要快速插入、刪除、查找的場景。
-
示例代碼：
Map<String, Integer> map = new HashMap<>(); map.put("apple", 3); int count = map.get("apple"); // O(1)
6. 樹（Tree）
-
特點：
- 層次結構：由節(jié)點和邊組成的分層數(shù)據(jù)結構。
-
分類：
- 二叉樹：每個節(jié)點最多有兩個子節(jié)點。
- 二叉搜索樹（BST）：左子節(jié)點小于父節(jié)點，右子節(jié)點大于父節(jié)點。
- 平衡樹：如紅黑樹、AVL樹，保持樹的平衡性。
-
適用場景：
- 實現(xiàn)高效的查找、排序、范圍查詢等。
-
示例代碼：
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } // 創(chuàng)建二叉樹節(jié)點 TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15);
7. 圖（Graph）
-
特點：
- 節(jié)點（頂點）和邊：表示物體和它們之間的關系。
-
表示方法：
- 鄰接矩陣：二維數(shù)組表示節(jié)點之間的連接。
- 鄰接表：每個節(jié)點的鄰居列表。
-
適用場景：
- 社交網(wǎng)絡、地圖導航、任務調度等。
-
示例代碼：
// 使用鄰接表表示圖 Map<String, List<String>> graph = new HashMap<>(); graph.put("A", Arrays.asList("B", "C")); graph.put("B", Arrays.asList("A", "D"));
8. 堆（Heap）
-
特點：
- 完全二叉樹：所有節(jié)點都滿足堆的性質。
- 大頂堆：每個父節(jié)點的值都大于等于其子節(jié)點。
- 小頂堆：每個父節(jié)點的值都小于等于其子節(jié)點。
-
適用場景：
- 實現(xiàn)優(yōu)先隊列、排序（堆排序）、求解 Top K 問題等。
-
示例代碼：
// 小頂堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.add(5); minHeap.add(2); int smallest = minHeap.poll(); // 2
9. 集合（Set）
-
特點：
- 元素唯一性：不包含重復元素。
-
適用場景：
- 去重操作、集合運算（交集、并集、差集）等。
-
示例代碼：
Set<String> set = new HashSet<>(); set.add("apple"); set.add("banana"); boolean exists = set.contains("apple"); // true
10. 字典樹（Trie）
-
特點：
- 前綴樹：用于高效地存儲和檢索字符串集合，尤其是字符串前綴共享的集合。
-
適用場景：
- 自動補全、拼寫檢查、前綴查詢等。
-
示例代碼：
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; }
三、算法復雜度
算法復雜度用于評估算法的性能，主要分為時間復雜度和空間復雜度。
1. 時間復雜度（Time Complexity）
- 定義：算法執(zhí)行所需時間與輸入規(guī)模之間的函數(shù)關系。
常見時間復雜度類型及示例
-
O(1) - 常數(shù)時間復雜度
描述：算法的執(zhí)行時間不隨輸入規(guī)模變化。
-
示例：訪問數(shù)組中的某個元素。
int getFirstElement(int[] arr) { return arr[0]; // O(1) }
-
O(log n) - 對數(shù)時間復雜度
描述：算法的執(zhí)行時間隨輸入規(guī)模的對數(shù)增長。
-
示例：二分查找。
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) - 線性時間復雜度
描述：算法的執(zhí)行時間與輸入規(guī)模成正比。
-
示例：遍歷數(shù)組。
int sumArray(int[] arr) { int sum = 0; for (int num : arr) { sum += num; // O(n) } return sum; }
-
O(n log n) - 線性對數(shù)時間復雜度
描述：常見于高效排序算法，如歸并排序、快速排序。
-
示例：歸并排序。
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) - 二次時間復雜度
描述：算法的執(zhí)行時間與輸入規(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; } } } }
時間復雜度優(yōu)先級排行（從高效到低效）
- O(1) - 常數(shù)時間
- O(log n) - 對數(shù)時間
- O(n) - 線性時間
- O(n log n) - 線性對數(shù)時間
- O(n2) - 二次時間
- O(2?) - 指數(shù)時間
- O(n!) - 階乘時間
2. 空間復雜度（Space Complexity）
- 定義：算法執(zhí)行過程中所需的額外空間與輸入規(guī)模之間的函數(shù)關系。
常見空間復雜度類型及示例
-
O(1) - 常數(shù)空間復雜度
描述：算法所需的額外空間不隨輸入規(guī)模變化。
-
示例：在原地交換兩個變量。
void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // O(1) 空間 }
-
O(n) - 線性空間復雜度
描述：算法所需的額外空間與輸入規(guī)模成正比。
-
示例：創(chuàng)建一個新數(shù)組存儲輸入數(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) - 二次空間復雜度
描述：算法所需的額外空間與輸入規(guī)模的平方成正比。
-
示例：創(chuàng)建一個二維矩陣。
int[][] matrix = new int[n][n]; // O(n2) 空間
空間復雜度優(yōu)先級排行（從高效到低效）
- O(1) - 常數(shù)空間
- O(log n) - 對數(shù)空間（通常出現(xiàn)在遞歸調用的?？臻g中）
- O(n) - 線性空間
- O(n log n)
- O(n2) - 二次空間
四、復雜度優(yōu)先級總結
-
時間復雜度優(yōu)先級（從高效到低效）：
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n2)
- O(2?)
- O(n!)
-
空間復雜度優(yōu)先級（從高效到低效）：
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n2)
數(shù)據(jù)結構：選擇合適的數(shù)據(jù)結構對于算法的效率至關重要。先了解所有常用的數(shù)據(jù)結構，然后深入理解其特點、操作和適用場景。
算法復雜度：時間復雜度和空間復雜度是衡量算法性能的兩個重要指標。了解各種復雜度類型及其優(yōu)先級，有助于在開發(fā)中選擇最優(yōu)的算法和數(shù)據(jù)結構。
