本文為力扣TOP100刷題筆記

筆者根據數據結構理論加上最近刷題整理了一套 數據結構理論加常用方法以下為該文章：

力扣外傳之數據結構（一篇文章搞定數據結構）

215. 數組中的第K個最大元素

class Solution {// 快速選擇遞歸函數int quickselect(int[] nums, int l, int r, int k) {if (l == r) return nums[k];  // 基準情況：區間只有一個元素// 選取基準值（這里簡單選擇最左邊的元素）int x = nums[l], i = l - 1, j = r + 1;// 分區操作while (i < j) {// 從左找第一個大于等于x的元素do i++; while (nums[i] < x);// 從右找第一個小于等于x的元素do j--; while (nums[j] > x);// 交換這兩個元素if (i < j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}// 遞歸處理包含第k元素的子區間if (k <= j) return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}public int findKthLargest(int[] _nums, int k) {int n = _nums.length;// 將問題轉化為找第n-k小的元素（即第k大的元素）return quickselect(_nums, 0, n - 1, n - k);}
}

算法步驟

1. 分區（Partition）：

   • 選擇一個基準值（pivot）x（這里選擇最左邊的元素nums[l]）

   • 使用兩個指針i和j：

     • i從左向右找第一個≥x的元素

     • j從右向左找第一個≤x的元素

     • 交換這兩個元素，直到i和j相遇

2. 遞歸選擇：

   • 根據k的位置決定遞歸處理左半部分還是右半部分

   • 如果k在左半部分（k <= j），繼續處理左半部分

   • 否則處理右半部分

3. 轉換問題：

   • 第k大的元素 = 第(n-k)小的元素（n - k）

示例演示

假設輸入數組為[3,2,1,5,6,4]，k = 2（找第2大的元素）：

1. n = 6，轉換為找第4小的元素（n - k = 4）

2. 初始調用quickselect(nums, 0, 5, 4)

3. 分區過程：

   • 基準值x = 3

   • i找到5，j找到1

   • 交換后數組變為[3,2,1,4,6,5]

   • j停在索引2

4. 因為4 > 2，遞歸處理右半部分quickselect(nums, 3, 5, 4)

5. 再次分區：

   • 基準值x = 4

   • i找到6，j找到4

   • 交換后數組不變

   • j停在索引3

6. 因為4 == 3，遞歸處理左半部分quickselect(nums, 3, 3, 4)

7. 直接返回nums[4] = 5

最終結果是5，即第2大的元素。

時間復雜度

• 平均情況：O(n)

• 最壞情況（每次選擇的基準值都是最大或最小值）：O(n2)

347. 前 K 個高頻元素

class Solution {public int[] topKFrequent(int[] nums, int k) {// 1. 使用哈希表統計每個數字出現的頻率Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// 2. 創建最小堆，按照出現頻率排序PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {return m[1] - n[1]; // 根據頻率比較}});// 3. 遍歷頻率哈希表，維護大小為k的最小堆for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {// 如果當前元素的頻率大于堆頂元素的頻率if (queue.peek()[1] < count) {queue.poll(); // 移除堆頂最小頻率元素queue.offer(new int[]{num, count}); // 加入當前元素}} else {queue.offer(new int[]{num, count});}}// 4. 從堆中提取結果int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[i] = queue.poll()[0]; // 取出數字部分}return ret;}
}

算法步驟

1. 統計頻率：

   • 使用哈希表occurrences記錄每個數字出現的次數

   • 遍歷數組，對每個數字的計數加1

2. 構建最小堆：

   • 創建優先隊列（最小堆），比較器基于頻率（數組的第二個元素）

   • 堆的大小限制為k，保持堆頂是當前k個元素中頻率最小的

3. 維護堆：

   • 遍歷頻率哈希表

   • 當堆未滿時，直接加入元素

   • 當堆已滿時，比較當前元素頻率與堆頂頻率

     • 如果當前頻率更高，替換堆頂元素

     • 否則跳過

4. 提取結果：

   • 從堆中依次取出元素，存入結果數組

   • 注意：由于是最小堆，取出的順序是從小到大，但不影響結果正確性

示例演示

假設輸入nums = [1,1,1,2,2,3]，k = 2：

1. 統計頻率：

   • occurrences = {1:3, 2:2, 3:1}

2. 構建堆過程：

   • 加入1:3 →?[(1,3)]

   • 加入2:2 →?[(2,2), (1,3)]

   • 處理3:1時堆已滿，3的頻率1小于堆頂2的頻率2，跳過

3. 提取結果：

   • 彈出(2,2)和(1,3)

   • 結果[2,1]（順序不重要）

時間復雜度分析

• 統計頻率：O(n)，n為數組長度

• 建堆操作：O(m log k)，m為不同數字的個數

  • 每個元素最多入堆一次，出堆一次

  • 堆操作時間復雜度為O(log k)

• 總時間復雜度：O(n + m log k)

空間復雜度

• 哈希表：O(m)

• 堆：O(k)

• 總空間復雜度：O(m + k)

優化建議

1. 當k接近m時：

   • 可以直接排序頻率哈希表，取前k個

   • 時間復雜度O(m log m)

2. 使用快速選擇：

   • 類似快速排序的分區思想

   • 平均時間復雜度O(n)，但實現更復雜

3. 并行處理：

   • 對于大規模數據，可以并行統計頻率

為什么使用最小堆？

最小堆能高效維護前k大的元素：

1. 堆的大小限制為k，空間效率高

2. 每次只需要比較堆頂元素，決定是否替換

3. 插入和刪除操作時間復雜度為O(log k)

這個實現很好地平衡了時間效率和代碼簡潔性，是解決Top K頻率問題的經典方法。