数组中的第K个最大元素

变量简洁正确完整思路
快速排序，dfs形参begend，将begend数组排序完毕，基准数nums[beg]，左右哨兵ij，j向中间找到小于nums[beg]的数，i向中间找到大于nums[beg]的数，交换ij，ij继续向中间找，直到i==j交换nums[beg],nums[i]，这样基准数处理完毕，左边小于基准数，右边大于基准数，已经将基准数处理完毕，只需要dfs(beg,i-1)dfs(i+1,end)将基准数左右两段数组都排序完毕就行，ifbeg<=end边界返回
修改：基准数处理完毕后，如果i==n-k直接结束，如果n-k<i去左边找，如果n-k>i去右边找
class Solution {
public:
    int ans=0,isok=false;
    int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();
        dfs(0,n-1,nums,n-k);
        return ans;
    }
    void dfs(int beg,int end,vector<int>&nums,int tar){
        if(isok)return;
        if(beg>end)return;
        int i=beg,j=end;
        while(i<j){
            while(nums[j]>=nums[beg]&&j>i)j--;
            while(nums[i]<=nums[beg]&&i<j)i++;
            if(i<j)swap(nums[i],nums[j]);
        }
        swap(nums[beg],nums[i]);
        if(i==tar){
            isok=true,ans=nums[i];
            return;
        }
        if(i>tar)dfs(beg,i-1,nums,tar);
        if(i<tar)dfs(i+1,end,nums,tar);
        
    }
};


变量简洁正确完整思路
堆排序，稍微修改
i需要处理，i-1已经大根堆，cur=i是可能破坏大根堆的节点，fa=(cur-1)/2，while
nums[cur]>nums[fa]说明cur破坏了大根堆，swap(nums[cur],nums[fa])，然后cur
更新为fa，继续检测cur是否破坏大根堆，处理完i数组是一个大根堆
j及j右边是已经排序好，逆向for遍历j，swap(nums[0],nums[j-1])，恢复大根堆
heapify(nums,int cur=0,n=j-1)，cur是可能破坏大根堆的节点，left=2*cur+1
right=2*cur+2，while()处理cur，找出cur，left，right最大的索引largestIndex
largestIndex是curbreak，否则swap(nums[largestIndex],nums[cur])
cur=largestIndex继续判断
修改：只需要得到前k次根结点就行了，也就是k到n里面的排好序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();

        for(int i=0;i<n;i++){
            int cur=i;
            int fa=(cur-1)/2;
            while(nums[cur]>nums[fa]){
                swap(nums[cur],nums[fa]);
                cur=fa;
                fa=(cur-1)/2;
            }
        }
        for(int j=n;j>(n-k)+1;j--){
            swap(nums[0],nums[j-1]);
            heapify(nums,0,j-1);
        }
        return nums[0];
    }
    void heapify(vector<int>&nums,int cur,int n){
        int left=cur*2+1,right=cur*2+2;
        while(left<n){
            int largestIndex=(nums[cur]>=nums[left])?cur:left;
            if(right<n&&nums[right]>nums[largestIndex])largestIndex=right;
            if(largestIndex==cur)break;
            swap(nums[cur],nums[largestIndex]);
            cur=largestIndex;
            left=cur*2+1,right=cur*2+2;
        }
    }
};