stellogic的个人空间
堆
stellogic Two
  2025-11-06 13:45:44   2025-11-06 13:45:44    

215. 数组中的第K个最大元素

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

方法：维护一个大小为 k 的小顶堆

核心思想

我们遍历整个数组，并始终维护一个包含 k 个元素的集合，这个集合里存的是我们到目前为止遇到的最大的 k 个数。遍历结束后，这个集合里的最小的那个数，就是整个数组中第 k 大的元素。

为了高效地实现这个思想，我们选择“小顶堆”作为存储这个集合的数据结构。

为什么是“小顶堆”？

  • 小顶堆 (Min-Heap)：一种数据结构，它的特点是堆顶永远是整个堆中最小的元素。
  • 为什么用它：我们用一个大小固定为 k 的小顶堆来存储“目前为止最大的k个数”。堆顶的元素自然就是这 k 个数中最小的那个。当来了一个新数字，我们只需要将它和堆顶元素比较：
    • 如果新数字比堆顶元素还小（或相等），那它肯定没资格进入“最大的k个数”的行列，直接忽略。
    • 如果新数字比堆顶元素大，说明它更有资格。我们就把堆顶的最小元素踢出去，把这个新数字加进来，维持堆的大小仍然是 k。

这样，我们只需要 O(log k) 的时间就能完成一次比较和替换操作。

详细步骤

  1. 初始化：创建一个小顶堆（在很多语言中也叫优先队列，设置为最小的元素优先级最高）。
  2. 遍历数组：逐个处理输入数组 nums 中的每一个数字 num。
  3. 维护堆：在处理每个数字 num 时，进行如下判断：
    • 如果堆内元素不足 k 个：直接将 num 放入堆中。
    • 如果堆内元素已有 k 个：
      • 获取堆顶元素 top（也就是当前已知的第 k 大的元素）。
      • 比较 num 和 top。
      • 如果 num > top，说明 num 比当前“第k大”的元素还要大，那么它有资格成为新的“k大元素”之一。此时，我们先从堆中移除堆顶元素 top，再将新元素 num 加入堆。
      • 如果 num <= top，说明 num 没有资格，我们什么都不做。
  4. 返回结果：当遍历完整个数组后，堆里剩下的就是整个数组中最大的 k 个元素。而堆顶的那个元素，就是这 k 个数中最小的，也就是我们最终要找的第 k 个最大的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int num : nums) {
            if (minHeap.size() < k){
                minHeap.offer(num);
            }else {
                if (num > minHeap.peek()){
                    minHeap.poll();
                    minHeap.offer(num);
                }
            }
        }
        return minHeap.peek();
    }
}

时间O(nlog(k))，空间O(k)

  1. 快速选择

    1. 对 n 个元素进行一次 分区 (Partition) 操作。这一步的成本依然是 O(n)。
    2. 分区后，基准 (pivot) 到位，假设它的索引是 p。
    3. 判断 p 和我们目标索引的关系 (我们要找的第 k 大的元素，在排序后数组中的索引是 n-k)。
      • 如果 p 正好是 n-k，那么我们找到了答案，算法结束。
      • 如果 p 大于 n-k，说明目标元素在基准的左边。我们只需要在左子数组中继续寻找。
      • 如果 p 小于 n-k，说明目标元素在基准的右边。我们只需要在右子数组中继续寻找。

和快排不同的是，我们直接抛弃了一半。平均情况就是n+(n/2)+(n/4)+……+1，求和后是O(N)

具体分区时，为了尽可能避免最坏情况，使用随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Random;

class Solution {
    private final Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int targetIndex = n - k;
        int left = 0;
        int right = n - 1;
        while (true){
            int pivotIndex = partition(nums,left,right);
            if (pivotIndex == targetIndex){
                return nums[pivotIndex];
            } else if (pivotIndex > targetIndex) {
                right = pivotIndex - 1;
            }else {
                left = pivotIndex + 1;
            }
        }
        
    }
    private int partition(int[]  nums,int left,int right){
        int randomIndex = random.nextInt(left,right+1);
        swap(nums,left,randomIndex);
        int i = left;
        int j = right;
        int pivot = nums[left];
        while (i < j){
            while (i < j && nums[j] >= pivot){
                j--;
            }
            if (i < j){
                nums[i] = nums[j];
            }
            while (i<j && nums[i] <= pivot){
                i++;
            }
            if (i < j){
                nums[j] = nums[i];
            }
        }
        nums[i] = pivot;
        return i;
    }
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

347. 前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

  1. 小顶堆法

使用一个哈希表统计频数

类似上一道topk问题

维护一个长度k的小顶堆。如果元素数目小于k直接入堆，否则和堆顶比，只要比堆顶大，就把堆顶出堆并且这个元素入堆,直到最后就是目标的k个元素。

（注意相等的时候也不操作，因为题目保证了频率最高的k个元素是唯一的。如果堆数目满足了k，并且堆顶和待测元素相等，最终必然两个都不在最终的目标集合里）

入堆出堆复杂度都是logk，最终复杂度nlogk

空间O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> frequencyMap = new HashMap<>();
        for (int num : nums){
            frequencyMap.put(num,frequencyMap.getOrDefault(num,0) + 1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> priorityQueue = new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer,Integer> entry : frequencyMap.entrySet()){
            if (priorityQueue.size() < k){
                priorityQueue.offer(entry);
            }else {
                if (entry.getValue() > priorityQueue.peek().getValue()){
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
            }
        }
        int [] result = new int[k];
        for (int i = 0;i < k;i++){
            result[i] = priorityQueue.poll().getKey();
        }
        return result;
    }
}
  1. 桶排序

先用哈希表统计频率

之后构造桶，桶索引代表频率，里面存的是频率为索引的元素

倒叙遍历桶，取出k个为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }


        List<Integer>[] buckets = new List[nums.length + 1];
        for (int i = 0; i < buckets.length;i++){
            buckets[i] = new ArrayList<Integer>();
        }
        
        
        for (Map.Entry<Integer,Integer> entry : frequencyMap.entrySet()){
            int frequency = entry.getValue();
            buckets[frequency].add(entry.getKey());
        }
        
        int[] result = new int[k];
        int index = 0;
        for (int i = buckets.length - 1;i >= 0 && index < k;i--){
            if (!buckets[i].isEmpty()){
                for (int num : buckets[i]){
                    if (index < k){
                        result[index++] = num;
                    }else {
                        break;
                    }
                }
            }
        }
        return result;
    }
}

时间复杂度:O(n+m+m+k),m是不同元素数目，总共还是O(n)

空间O(n)

  1. 快速选择

    1. 统计频率：使用 HashMap 统计数组 nums 中每个元素的出现频率。
    2. 提取唯一元素：将 HashMap 中的所有键（即唯一元素）存入一个列表中。
    3. 执行快速选择：
      • 我们的目标是找到频率最高的 k 个元素。这等价于：如果我们将所有唯一元素按其频率从小到大排序，那么我们需要的 k 个元素就位于排序后列表的末尾。
      • 具体来说，如果共有 m 个唯一元素，那么频率第 k 高的元素的最终位置应该在索引 m - k 处。
      • 快速选择算法的目的就是高效地找到这个“分割点”，使得位于索引 m - k 的元素就位，并且所有在它右边的元素的频率都比它大（或相等），所有在它左边的元素的频率都比它小（或相等）。
      • 我们无需对整个列表进行完全排序，只需要保证这 k 个元素被移动到列表的右侧即可。
    4. 返回结果：返回列表右侧的 k 个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

class Solution {
    private int[] uniqueNums;
    private Map<Integer,Integer> frequenceMap;

    public int[] topKFrequent(int[] nums, int k) {
        frequenceMap = new HashMap<>();
        for (int num : nums) {
            frequenceMap.put(num,frequenceMap.getOrDefault(num,0)+1);
        }
        
        
        int m = frequenceMap.size();
        uniqueNums = new int[m];
        int i = 0;
        for (int num : frequenceMap.keySet()){
            uniqueNums[i++] =  num;
        }
        
        quickSelect(0,m-1,m-k);
        
        int[] result = new int[k];
        System.arraycopy(uniqueNums,m-k,result,0,k);
        return result;
    }
    
    private void quickSelect(int left,int right,int targetIndex){
        while (left < right){
            int pivotIndex = partition(left,right);
            if (pivotIndex == targetIndex){
                return;
            }else if (pivotIndex < targetIndex){
                left = pivotIndex+1;
            }else {
                right = pivotIndex - 1;
            }
        }
    }
    
    private int partition(int left,int right){
        Random random = new Random();
        int pivotIndex = random.nextInt(left,right+1);
        int pivotFrequence = frequenceMap.get(uniqueNums[pivotIndex]);
        swap(right,pivotIndex);


        int slow = left - 1;
        int fast = left;
        
        while (fast < right){
            int frequence = frequenceMap.get(uniqueNums[fast]);
            if (frequence <= pivotFrequence){
                slow++;
                swap(slow,fast);
            }
            fast++;
        }
        swap(slow+1,right);
        return slow+1;
    }
    
    private void swap(int i ,int j){
        int temp = uniqueNums[i];
        uniqueNums[i] = uniqueNums[j];
        uniqueNums[j] = temp;
    }
}

时间平均是O(n)

空间O(n)

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
提示:

-105 <= num <= 105
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 104 次调用 addNum 和 findMedian

用列表### 更优的解法：双堆（最大堆 + 最小堆）

这道题最经典和高效的解法是使用两个堆：

  1. 一个 最大堆 (Max Heap)
  2. 一个 最小堆 (Min Heap)

核心思想：

  • 我们维护两个堆，使得数据流中的所有数字被分成两半。
  • 最大堆 maxHeap 用于存储数据流中较小的那一半数字。
  • 最小堆 minHeap 用于存储数据流中较大的那一半数字。

通过维持以下两个平衡条件，我们就可以在 O(1) 的时间内获取中位数：

  1. maxHeap 中的所有元素都小于或等于 minHeap 中的所有元素。
  2. 两个堆的大小尽可能相等，否则maxHeap比minHeap多1。

如何工作：

  • addNum(num):

    1. 将新数字 num 加入 maxHeap。
    2. 为了维持平衡条件1，将 maxHeap 的堆顶（最大值）弹出，并加入到 minHeap 中。
    3. 为了维持平衡条件2，如果 maxHeap 的大小小于 minHeap，则将 minHeap 的堆顶（最小值）弹出，并加入到 maxHeap 中。

  • findMedian():

    • 如果两个堆的大小相等（说明总元素个数是偶数），中位数就是两个堆顶元素的平均值：(maxHeap.top() + minHeap.top()) / 2。
    • 如果 maxHeap 比 minHeap 多一个元素（说明总元素个数是奇数），中位数就是 maxHeap 的堆顶元素。
      存储数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.List;
import java.util.PriorityQueue;

class MedianFinder {


    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b - a);


    
    public void addNum(int num) {
        maxHeap.add(num);
        int temp = maxHeap.poll();
        minHeap.add(temp);
        if (maxHeap.size() < minHeap.size()){
            int min_poll = minHeap.poll();
            maxHeap.offer(min_poll);
        }
        
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()){
            return (maxHeap.peek()+minHeap.peek())/2.0;
        }else {
            return (double) maxHeap.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

每次add复杂度：O(logn)

查找中位数:O（1）

空间O(n)

堆
2025/11/06/堆/
作者
stellogic
发布于
2025-11-06 13:45
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 215. 数组中的第K个最大元素
    1. 1.1. 方法：维护一个大小为 k 的小顶堆
      1. 1.1.1. 核心思想
      2. 1.1.2. 为什么是“小顶堆”？
    2. 1.2. 详细步骤
  2. 2. 347. 前 K 个高频元素
  3. 3. 295. 数据流的中位数
  1. 1. 215. 数组中的第K个最大元素
    1. 1.1. 方法：维护一个大小为 k 的小顶堆
      1. 1.1.1. 核心思想
      2. 1.1.2. 为什么是“小顶堆”？
    2. 1.2. 详细步骤
  2. 2. 347. 前 K 个高频元素
  3. 3. 295. 数据流的中位数