本文共 1677 字，大约阅读时间需要 5 分钟。

题目描述

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路

• 小顶推方式

建一个只能存K个数字的小顶堆，超过K时候，每加进来一个，堆顶就要弹出一个。数组遍历完，最终堆顶的元素就是第K大的（堆里其他元素都比他还要大）。

• 快速选择方式

的平均时间复杂度为 O(N)。就像快速排序那样，本算法也是 Tony Hoare 发明的，因此也被称为 Hoare选择算法。

本方法大致上与快速排序相同。简便起见，注意到第 k 个最大元素也就是第 N - k 个最小元素，因此可以用第 k 小算法来解决本问题。

首先，我们选择一个枢轴，并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。

为了实现划分，沿着数组移动，将每个元素与枢轴进行比较，并将小于枢轴的所有元素移动到枢轴的左侧。

这样，在输出的数组中，枢轴达到其合适位置。所有小于枢轴的元素都在其左侧，所有大于或等于的元素都在其右侧。

这样，数组就被分成了两部分。如果是快速排序算法，会在这里递归地对两部分进行快速排序，时间复杂度为 O(NlogN)。

而在这里，由于知道要找的第 N - k 小的元素在哪部分中，我们不需要对两部分都做处理，这样就将平均时间复杂度下降到 O(N)。

最终的算法十分直接了当 :

随机选择一个枢轴。

使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边。

比较 pos 和 N - k 以决定在哪边继续递归处理。

! 注意，本算法也适用于有重复的数组

AC

采用小顶推方式：

class Solution {
   public:    int findKthLargest(vector
   
    & nums, int k) {
           priority_queue
    
     
      ,greater
      
       > q;        for(auto it:nums){
               q.push(it);            if(q.size()>k) q.pop();        }        return q.top();    }};
      
     
    
   

采用快速选择方式：

class Solution {
   public:    int findKthLargest(vector
   
    & nums, int k) {
           int start=0,end=nums.size()-1,target=nums.size()-k;        while(start
    
     mid) start=mid+1;            else end=mid-1;        }        return nums[start];    }    int quickSelect(vector
     
      & nums,int p,int q){
           int i=p+1,j=q;        int x=nums[p];        while(1){
               while(i
      p && nums[j]>=x) --j;            if(i>=j) break;            swap(nums[i],nums[j]);        }        swap(nums[p],nums[j]);        return j;    }};
     
    
   

转载地址：https://chocolate.blog.csdn.net/article/details/106214462 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！