Interview Classic 150 Questions P215 Kth Largest Element in an Array

---

Timeline

timeline

2025-12-05

init

quick sort, heap

---

Title:

P215 the Kth in the arrayKlargest element

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

heap sort

forcomplete binary treenumber the nodes, with the following relationship

Item	1-based numbering(root=1)	0-based indexing(root=0)
left child	$\text{left}(i)=2i$	$\text{left}(i)=2i+1$
right child	$\text{right}(i)=2i+1$	$\text{right}(i)=2i+2$
parent node	$\text{parent}(i)=\lfloor i/2 \rfloor（i>1）$	$\text{parent}(i)=\lfloor (i-1)/2 \rfloor（i>0）$
condition for having at least a left child	$2i \le n$	$2i+1 < n$
condition for existence of right child	$2i+1 \le n$	$2i+2 < n$
leaf node condition	$i > \lfloor n/2 \rfloor$	$i > \lfloor (n-2)/2 \rfloor$ or$2i+1 \ge n$
condition for having only left child	$2i = n$	$2i+1 < n$ and $2i+2 \ge n$
depth (root level=1)	$\lfloor \log_2 i \rfloor +1$	$\lfloor \log_2 (i+1) \rfloor +1$
depth (root level=0)	$\lfloor \log_2 i \rfloor$	$\lfloor \log_2 (i+1) \rfloor$

Heap sort:

#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]);
                        //Since the parent and child nodes have been swapped, it may affect the subtree of the child node, so adjust the subtree of the child node.
                        heapify(vec, largest, n);
                }
        }

        void buildMaxHeap(vector<int> &vec)
        {
                int n = vec.size();
                // The position of the last node is n-1, so the position of the parent node is (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];
        }
};

Quick sort

Note that the Hoare partition scheme does not care where elements equal to the pivot are, only requires left <= pivot and right >= 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();
                // The K-th largest is the (n-k)-th smallest.
                return quick_sort(nums, 0, n - 1, n - k);
        }
};