面试经典150题 P215 数组中的第K个最大元素

---

时间轴

时间轴

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$

堆排序:

#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

#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);
        }
};