时间轴

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）
左孩子 $\text{left}(i)=2i $ $ \text{left}(i)=2i+1 $
右孩子 $ \text{right}(i)=2i+1 $ $ \text{right}(i)=2i+2 $
父节点 $ \text{parent}(i)=\lfloor i/2 \rfloor（i>1）$ $ \text{parent}(i)=\lfloor (i-1)/2 \rfloor（i>0）$
至少有左孩子的条件 $ 2i \le n $ $ 2i+1 < n $
右孩子存在条件 $ 2i+1 \le n $ $ 2i+2 < n $
叶节点条件 $i > \lfloor n/2 \rfloor$ $ i > \lfloor (n-2)/2 \rfloor $或 $2i+1 \ge n$
只有左孩子条件 $2i = n $ $ 2i+1 < n $ 且 $ 2i+2 \ge n $
深度（root 层=1） $ \lfloor \log_2 i \rfloor +1 $ $ \lfloor \log_2 (i+1) \rfloor +1 $
深度（root 层=0） $ \lfloor \log_2 i \rfloor $ $ \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, left..=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);
        }
};