leetcode hot100刷题日记——23.数组中的第K个最大元素

解答：
方法一：快排延申

class Solution {
public:

    int quickselect(vector<int>&nums,int l,int r,int k){
        if(l==r)
            return nums[k];//当l=r时，划分得到的就是我们需要的下标
        int partiton=nums[l],i=l-1,j=r+1;
        while(i<j){
            do i++; while(nums[i]<partiton);//如果nums[i]<基准元素，那么nums[i]按理来说应该放在基准元素左边
            //i++相当于给nums[i]占个位置的感觉
            do j--; while(nums[j]>partiton);//如果nums[j]>基准元素，那么nums[j]按理来说应该放在基准元素右边
            //j--相当于给nums[j]占个位置的感觉
            if(i<j){//最后如果i<j，说明l到r中间还没遍历完，nums[i]>nums[j]
            //所以要交换顺序后再继续遍历确定基准元素位置
                swap(nums[i],nums[j]);
            }
        }
        //如果k<=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);//为什么是n-k？
        //根据快排的划分后，我们一定可以确定一个元素的最终位置，比如x的最终位置是q
        //那么a[l,……,q-1]这些元素都<=a[q]
        //a[q+1,……,r]这些元素都>=a[q]
        //所以只要划分的q是倒数第k个下标，就可以得到答案
    }
};

时间复杂度：O(n)
空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为 O(logn)

这个时间复杂度让我们来详解一下：
快速选择算法是快速排序算法的一个变种，用于在一个无序数组中找到第 k 小的元素（或第 k 大的元素）。它通过递归划分数组来逐步缩小问题规模，直到找到目标元素。

快速选择算法的平均时间复杂度分析
（1）划分操作的时间复杂度：
每次划分操作的时间复杂度为 O(n)，因为它需要遍历整个数组来确定基准元素的最终位置。
在划分过程中，我们比较每个元素与基准元素的大小，并将它们分成左右两部分。
（2）递归深度分析：
在快速选择算法中，每次划分操作将数组分成两个子数组。一个子数组包含小于基准元素的元素，另一个包含大于基准元素的元素。
我们只需要对其中一个子数组进行递归处理，因为目标元素一定在其中一个子数组中。
（3）递归调用的期望时间复杂度：
假设每次划分操作都能将数组分成一个大小为 n/2 的子数组和一个大小为 n/2 - 1 的子数组（这是理想情况下的均衡划分）。
在这种情况下，递归调用的深度为 log₂n。
（4）总时间复杂度推导：
每层的时间复杂度为 O(n)，因为划分操作的时间复杂度为 O(n)。
递归调用的深度为 log₂n，因此总时间复杂度为 O(n) × O(log n) = O(n log n)。然而，快速选择算法在每次递归调用中只处理一个子数组，而不是像快速排序那样处理两个子数组。
因此，实际的总时间复杂度更接近于 O(n)。
（5）数学归纳法证明：
设 T(n) 为处理 n 个元素的时间复杂度，满足递推式 T(n) = T(n/2) + O(n)。
使用主定理（Master Theorem）来求解这个递推式：
主定理的条件：T(n) = aT(n/b) + O(n^d)，其中 a ≥ 1，b > 1，d ≥ 0。
在快速选择的情况下，a = 1（每次递归只处理一个子数组），b = 2，d = 1。
根据主定理，当 a = b^d 时，T(n) = O(n^d log n)。但在快速选择中，a = 1，b^d = 2^1 = 2，因此不满足这个条件。
实际上，快速选择的递推式 T(n) = T(n/2) + O(n) 的解为 T(n) = O(n)。这是因为每次递归调用处理的子数组大小减半，总时间复杂度为 O(n) + O(n/2) + O(n/4) + … + O(1) = O(n)。

方法二：堆

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        //计算左子节点和右子节点的索引，并初始化 largest 为当前节点 i
        int l=2*i+1,r=2*i+2,largest=i;
        if(l<heapSize&&a[l]>a[largest]){
            largest=l;
        }
        if(r<heapSize&&a[r]>a[largest]){
            largest=r;
        }
        // 如果最大的值不是当前节点，则交换它们的位置，并递归调用 maxHeapify 函数，以确保交换后的子树仍然满足最大堆的性质
        if(largest!=i){
            swap(a[i],a[largest]);
            maxHeapify(a,largest,heapSize);
        }
    }
    void buildMaxHeap(vector<int>&a,int heapSize){
        // 从最后一个父节点开始（索引为 heapSize/2-1），向上遍历到根节点（索引为 0）
        for(int i=heapSize/2-1;i>=0;--i){
            // 调用 maxHeapify 函数对每个父节点进行堆化处理，确保整个数组满足最大堆的性质
            maxHeapify(a,i,heapSize);
        }
    }
    //构建大根堆，做k-1次删除操作后，堆顶元素就是答案
    int findKthLargest(vector<int>& nums, int k) {
        int heapSize=nums.size();
        buildMaxHeap(nums,heapSize);
        //从nums.size()-1到nums.size()-1-(k-2)，做了k-1从删除操作
        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];
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(logn)

方法三：题解中还看见了一个特别灵活的小顶堆，通过维护一个大小为 k 的小顶堆实现的

class Solution {
public:
    void adjust(vector<int>& heap, int cur) {
        int l = 2 * cur + 1, r = 2 * cur + 2, minn = cur;
        if (l < heap.size() && heap[l] < heap[minn]) minn = l;
        if (r < heap.size() && heap[r] < heap[minn]) minn = r;
        if (minn != cur) {
            swap(heap[minn], heap[cur]);
            adjust(heap, minn);
        }
    }

    void build(vector<int>& heap) {
        for (int i = heap.size() / 2 - 1; i >= 0; --i) {
            adjust(heap, i);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(nums.begin(), nums.begin() + k); // 复制前 k 个元素
        build(heap); // 建立小顶堆

        for (int i = k; i < nums.size(); ++i) {
            if (nums[i] > heap[0]) {
                heap[0] = nums[i]; // 替换堆顶元素
                adjust(heap, 0); // 调整堆
            }
        }

        return heap[0]; // 返回堆顶元素，即第 k 大的元素
    }
};