数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

❤❤❤基于快排的快速选择（递归（选择判断->pivot获取->partition）和双指针）

思路

快速排序为典型的分治算法，对a[l...r]排序的过程可以分解如下：

1. 分解：取任意下标pivot，并将数组划分成两个子数组，a[l...pivot-1]（元素均<=a[pivot]）和a[pivot+1...r]（元素均>a[pivot]）。
2. 解决：对子数组a[l...pivot-1]和a[pivot+1...r]重复执行(1)
3. 合并：将子数组合并，若为原址排序，不需要这一步。

   算法

   由于每次分解都可以得到从小大到排序的第pivot+1个数，且第k个最大元素实为从小到大排序第n-k个数，故如下：

• 若pivot==n-k时，则返回nums[pivot];
• 若pivot<n-k时，递归a[pivot+1...r]
• 若pivot>n-k时，递归a[l...pivot+1]

  实现-递归

  ```cpp int quickSelect(vector& nums,int l,int r,const int idx){ int curIdx=randomQS(nums,l,r); if(curIdx==idx){

    return nums[curIdx];

  } else{

    return curIdx<idx?quickSelect(nums,curIdx+1,r,idx):quickSelect(nums,l,curIdx-1,idx);

  } } int randomQS(vector& nums,int l,int r){ //基于随机值来选取pivot int pivot=rand()%(r-l+1)+l; swap(nums[pivot],nums[r]); return patition(nums,l,r); } int __patition(vector& nums,int l,int r){ //根据x值来划分左右区间，满足左边<=x<右边 int x=nums[r],j=l-1; for(int i=l;i<r;i++){

    if(nums[i]<=x){
        //j保留pivot左侧的位置
        swap(nums[i],nums[++j]);
    }

  } swap(nums[++j],nums[r]); return j; } int findKthLargest(vector& nums, int k) { srand(time(0));//保证每次随机值不相同 return __quickSelect(nums,0,nums.size()-1,nums.size()-k); }

//寻找中位数 int __median_of_three(const vector& arr,const int i,const int j,const int k) const{ int a=arr[i],b=arr[j],c=arr[k]; if(a>b){ if(b>c) return j; //b; else if(a>c) return k; //c; else return i; //a; } else{//a<=b if(a>c) return i; //a; else if(b>c) return k; //c; else return j; //b; } }

<a name="1oOD6"></a>
### 实现-双指针
```cpp
int findKthLargest(vector<int>& nums, int k){
    srand(time(0));
    k=num.size()-k;
    int l=0,r=nums.size()-1;
    while(l<r){
        int rlt=quickSort(nums,l,r);
        if(rlt==k) break;
        else if(rlt<l) l=rlt+1;
        else r=rlt-1;
    }
    return nums[k];
}
int quickSort(vector<int>& a,int l,int r){
    int __cnt=rand()%(r-l+1)+l;
    swap(nums[l],nums[__cnt]);
    int pivot=l;
    while(l<r){
        while(nums[r]>=nums[pivot] && r>l) r--;
        while(nums[l]<=nums[pivot] && r>l) l++;
        swap(nums[l],nums[r]);
    }
    swap(nums[pivot],nums[l]);
    return l;
}

复杂度分析

• 时间复杂度:
• 空间复杂度:

我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n - 1，每次递归的时候又向 n - 1 的集合中递归，这种情况是最坏的，时间代价是 。我们可以引入随机化来加速这个过程，它的时间代价的期望是 ，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」

❤❤基于堆排序的选择方法(建堆-调整堆)

建堆的方法核心在：递归交换，堆实质上是【父-左右孩子】约束关系形成的数据结构 在第一次建堆时，需要从下往上递归的进行交换，以后每次添加或删除，都仅需要从上到下进行一次递归交换 当建堆完成时：

• 对于pop，将根元素=最后一个元素，并从上到下递归交换（数组长度-1后交换）
• 对于push，数组push_back后，从上到下递归交换（数组长度+1后交换）

思路

注意，每次交换后，都需要对下一层的子堆递归调整，因为交换后破坏了已调整的子堆结构。
假设将数组[0,1,2,3,4,...,n-1]看作一个完全二叉树，则对应父节点i，有

• 左孩子：2*i+1
• 右孩子: 2*i+2

大根堆的调整方法（递归交换）：

从根节点开始

1. 对当前【父节点-左/右孩子】实施交换，并在下一层交换处（若为大根堆，则为左右子树大者）递归实施交换。
2. 递归到最后一个非叶子节点时结束。

大根堆的建树方法：

1. 从最后一个非节点开始实施递归交换
2. 直到根节点时结束。

   算法

• 交换:maxHeapify(arr,i,last)

递归的实现【父节点-左/右孩子】的交换

• 弹出：

1. 将root以大根堆的最后一个元素替换。
2. 实施一次maxHeapify(arr,0,last)

   实现

   ```cpp / 从根节点开始递归调整 / void __maxHeapify(vector& nums,int i,int heapSize){ int l=2i+1,r=2i+2,bigger=i; if(lnums[bigger]){

    bigger=l;

   } if(rnums[bigger]){

    bigger=r;

   } if(i!=bigger){

    /* 若当前节点调整，则递归调整下一层 */
    swap(nums[i],nums[bigger]);
    __maxHeapify(nums,bigger,heapSize);

   } }

/ 建树-从最后一个非根节点开始实施递归交换 / / 最后一个非根节点 ： headSize/2 / void buildHeap(vector& nums,int heapSize){ for(int i=(heapSize>>1);i>=0;i—){ maxHeapify(nums,i,heapSize); } }

int findKthLargest(vector& nums, int k) { int N=nums.size(); buildHeap(nums,N); //pop() k个点 int popId=N-1; while(—k){ nums[0]=nums[popId]; maxHeapify(nums,0,—N); —popId; } return nums[0]; } ```

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分