时间轴

2025-12-05

init

题目：

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

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-interview-150

堆排序

对完全二叉树结点进行编号，有如下关系

项目 1-based 编号（根=1） 0-based 编号（根=0）
左孩子 left(i)=2i\text{left}(i)=2i left(i)=2i+1 \text{left}(i)=2i+1
右孩子 right(i)=2i+1 \text{right}(i)=2i+1 right(i)=2i+2 \text{right}(i)=2i+2
父节点 parent(i)=⌊i/2⌋（i>1） \text{parent}(i)=\lfloor i/2 \rfloor（i>1） parent(i)=⌊(i−1)/2⌋（i>0） \text{parent}(i)=\lfloor (i-1)/2 \rfloor（i>0）
至少有左孩子的条件 2i≤n 2i \le n 2i+1<n 2i+1 < n
右孩子存在条件 2i+1≤n 2i+1 \le n 2i+2<n 2i+2 < n
叶节点条件 i>⌊n/2⌋i > \lfloor n/2 \rfloor i>⌊(n−2)/2⌋ i > \lfloor (n-2)/2 \rfloor 或 2i+1≥n2i+1 \ge n
只有左孩子条件 2i=n2i = n 2i+1<n 2i+1 < n 且 2i+2≥n 2i+2 \ge n
深度（root 层=1） ⌊log⁡2i⌋+1 \lfloor \log_2 i \rfloor +1 ⌊log⁡2(i+1)⌋+1 \lfloor \log_2 (i+1) \rfloor +1
深度（root 层=0） ⌊log⁡2i⌋ \lfloor \log_2 i \rfloor ⌊log⁡2(i+1)⌋ \lfloor \log_2 (i+1) \rfloor

堆排序:

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
#include <vector>
using std::vector;

class Solution {
    private:
        void heapify(vector<int> &vec, int curr, int n)
        {
                int left = curr * 2 + 1;
                int right = curr * 2 + 2;
                int largest = curr;

                if (left < n && vec[left] > vec[largest]) {
                        largest = left;
                }

                if (right < n && vec[right] > vec[largest]) {
                        largest = right;
                }

                if (largest != curr) {
                        std::swap(vec[largest], vec[curr]);
                        //由于交换了父节点和子节点，因此可能对子节点的子树造成影响，所以对子节点的子树进行调整。
                        heapify(vec, largest, n);
                }
        }

        void buildMaxHeap(vector<int> &vec)
        {
                int n = vec.size();
                // 最后一个节点的位置为n-1，所以父节点的位置为(n-1-1)/2。
                for (int i = (n - 2) / 2; i >= 0; i--) {
                        heapify(vec, i, n);
                }
        }

    public:
        int findKthLargest(vector<int> &nums, int k)
        {
                int n = nums.size();
                buildMaxHeap(nums);

                for (int i = 0; i < k - 1; i++) {
                        // pop
                        std::swap(nums[0], nums[n - 1]);
                        n--;
                        heapify(nums, 0, n);
                }
                return nums[0];
        }
};

快速排序

注意 hoare 写法不关心与 pivot 相等的在哪，只要求左边<= pivot, 右边>= pivot

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
#include <vector>
using std::vector;
class Solution {
    private:
        int quick_sort(vector<int> &nums, int start, int end, int k)
        {
                if (end <= start) {
                        return nums[k];
                }
                int pivot = nums[(start + end) / 2];
                int left = start - 1;
                int right = end + 1;
                while (left < right) {
                        do {
                                left++;
                        } while (nums[left] < pivot);
                        do {
                                right--;
                        } while (nums[right] > pivot);
                        if (left < right) {
                                std::swap(nums[left], nums[right]);
                        }
                }
                // start..=right, right+1..=end
                if (k<= right) {
                        return quick_sort(nums, start, right, k);
                } else {
                        return quick_sort(nums, right+1, end, k);
                }
        }

    public:
        int findKthLargest(vector<int> &nums, int k)
        {
                int n = nums.size();
                // 第K个最大，即第n-k最小
                return quick_sort(nums, 0, n - 1, n - k);
        }
};