day7 数组中的第K个最大元素

休息了两天，开始继续写题。
记得完成自适应光学、信息论和智能图像处理的作业。

  • [x] 自适应光学
  • [ ] 信息论
  • [ ] 智能图像处理

读题

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

要求有二：
一是需要满足条件找到指定的数，二是对时间复杂度有要求。

思路

第一思路

给了 vector，于是想到对数组排序后直接取数；但是要求 O(n) 时间复杂度，也就是如果要遍历的话只能遍历一遍或有限遍。
如果遍历 k 遍，每遍得到一个最大值，那么复杂度是 O(kn)（大概）。
于是过程：

  1. 循环 k 次；创建一个等长的全 0 空数组
    1. 第 i 次循环
    2. 跳过空数组对应位置不为 0 的位置
    3. 遇到的最大值为 max_num，记录对应位置，将空数组对应位置标记为 i
    4. 继续

考虑到 k 可能会比较大，如果 k 大于 size_nums 的一半，则改为找最小值。

于是有代码：

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int size_nums = nums.size();
        if(k<size_nums-k){
            vector<int> max_nums(size_nums);
            int max_num = 0;
            int pos = -1;
            for(int i=0;i<=k;i++){
                max_num = 0;
                pos = -1;
                for(int j=0;j<size_nums;j++){
                    if(max_nums[j]!=0) continue;
                    max_num = max_num>nums[j]?max_num:nums[j];
                    pos = max_num>nums[j]?pos:j;
                }
                max_nums[pos]=i;
            }
            return max_num;
        }else{
            vector<int> min_nums(size_nums);
            k = size_nums-k;
            int min_num = 0;
            int pos = -1;
            for(int i=0;i<=k;i++){
                min_num=114514;
                pos = -1;
                for(int j=0;j<size_nums;j++){
                    if(min_nums[j]!=0) continue;
                    min_num = min_num<nums[j]?min_num:nums[j];
                    pos = min_num<nums[j]?pos:j;
                }
                min_nums[pos]=i;
            }
            return min_num;
        }
    }
};

没超时，不过在一个小数列处出错了；于是把 k<size_nums-k 改成了 k<=size_nums-k。
现在在包含负数的地方出错了，应该是 max_num 初始化的问题？测试用例是 [-1,2,0]，k 是 2，结果是 0，我输出是 -1。
哦，不是，是我在 k>size_nums-k 时这部分的判断问题。第 k 大应当对应第 size_nums-k+1 小（比方说大小为 3 的数组中，第 2 大应该是第 2 小），而不是第 size_nums-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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int size_nums = nums.size();
        if(k<=size_nums-k){
            vector<int> max_nums(size_nums);
            int max_num;
            int pos;
            for(int i=0;i<=k;i++){
                max_num = -114514;
                pos = -1;
                for(int j=0;j<size_nums;j++){
                    if(max_nums[j]!=0) continue;
                    max_num = max_num>nums[j]?max_num:nums[j];
                    pos = max_num>nums[j]?pos:j;
                }
                max_nums[pos]=i;
            }
            return max_num;
        }else{
            vector<int> min_nums(size_nums);
            k = size_nums-k+1;
            int min_num;
            int pos;
            for(int i=0;i<=k;i++){
                min_num=114514;
                pos = -1;
                for(int j=0;j<size_nums;j++){
                    if(min_nums[j]!=0) continue;
                    min_num = min_num<nums[j]?min_num:nums[j];
                    pos = min_num<nums[j]?pos:j;
                }
                min_nums[pos]=i;
            }
            return min_num;
        }
    }
};

提交，然后不出所料地超时了。这个测试用例的 nums 巨大一坨，size 是 35107，k 是 15991，也就是在中间，刚好是我最怕的那种。
这题 k 是 n/2，那么我的复杂度就成了 O(n^2) 了。

改变思路

需要 O(n)，我的直觉告诉我用之前遇到过的单调栈来解。但是怎么解？
维护一个容量为 k 的单调栈，栈顶最小，栈底最大。

  1. num 大于栈顶的数字吗？
    1. 是。
      1. 栈顶出栈，重新判断，直到 num 小于栈顶元素。
    2. 否。
      1. 栈是否已满？
        1. 是
          1. 继续前进。
        2. 否
          1. num 入栈。

于是有代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        stack<int> s;
        int size_nums = nums.size();
        for (int i = 0; i < size_nums; i++) {
            if (s.empty()) // 相当于初始化
                s.push(nums[i]);
            if (nums[i] > s.top()) {
                i--;
                s.pop();
                continue;
            } else {
                if (s.size() >= k)
                    continue;
                else {
                    s.pop();
                    s.push(nums[i]);
                }
            }
        }
        return s.top();
    }
};

但是发现无法满足“筛选出最大的 k 的元素要求”，因为只能看到栈顶元素；如果一直出栈，那就会导致之前的元素都被丢掉。如果记录并重新入栈，则会导致时间复杂度飙升。

再次改变思路

首先，明白我需要什么。不能强行使用单调栈这种不适合的数据结构。我需要的是一个能存储包含 k 个数据的单调数据结构。假如有一个数据结构叫 ASD，有最大大小 k，那么我需要的是：

  1. ASD 是否为满？
    1. 不为满
      1. 当前元素是最大的/最小的吗？
        1. 是：
          1. 直接放在开头/结尾
        2. 否：
          1. 插入
    2. 为满：
      1. 插入

但是插入到正确位置这个过程最大难免会有 O(k) 复杂度。有什么数据结构能满足我的要求？还是说我的思路是错误的？

官方题解

不是我能做出来的题，直接看题解。
官方题解的都是 O(nlogn) 的时间复杂度，题干里却要求 O(n)， 评论直接骂说左右脑互博。还有评论说直接秒解：

1
2
3
4
public int findKthLargest(int[] nums, int k) {
	Arrays.sort(nums);
	return nums[nums.length - k];
}

难绷。难道他是天才？

方法一：快速排序

类似于我的第一反应：先排序，后定位。但是使用的是快速排序，所以单次的时间复杂度是 O(logn) 而不是 O(n)。上面那个 Arrays.sort(nums) 应该就是 java 的快速排序库函数。

有官方代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

不是我说，这几乎就是自己搓了一个 qsort 吧？不过 cpp 中似乎没有 qsort。搜了一下发现 qsort 用的也是快速排序。

方法二：基于堆排序的选择方法

见过但是不记得的数据结构：堆。有定义：
堆（英语：heap) 是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。
    将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

确实是自带排序、方便维护和搜索的数据结构。

有官方代码：

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
class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

收获

  1. 堆
  2. 快速排序
  3. 复习了单调栈（虽然没有用上）
day7 数组中的第K个最大元素
http://blog.wspdwzh.space/2025/10/26/day7-第K个最大元素/
作者
peter？
发布于
2025年10月26日
许可协议