精选力扣500题第3题 LeetCode 215. 数组中的第K个最大元素【c++详细题解】

悠悠 2021-07-24 11:46 223阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路1
         *  3、思路2
         *  4、代码

### 1、题目 ###

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

**示例 1:**

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

**示例 2:**

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

**说明:**

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

### 2、思路1 ###

**快速排序**  O ( l o g n ) O(logn) O(logn)

将数组使用快速排序重新排列一遍，然后输出`nums[n-k]`

### 3、思路2 ###

**快速选择**  O ( n ) O(n) O(n)

快选是在快排的基础上只递归一半区间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
如果当前要找的数 > = x >=x >=x则递归左区间，否则递归右区间。

### 4、代码 ###

class Solution { 
    public:
    
        int quick_sort(vector<int>& nums, int l, int r, int k) { 
            if (l == r) return nums[l];
            int x = nums[l], i = l - 1, j = r + 1;
            while (i < j) { 
                do i ++ ; while (nums[i] > x);
                do j -- ; while (nums[j] < x);
                if (i < j) swap(nums[i], nums[j]);
            }
            if (k <= j) return quick_sort(nums, l, j, k);
            else return quick_sort(nums, j + 1, r, k);
        }
    
        int findKthLargest(vector<int>& nums, int k) { 
            return quick_sort(nums, 0, nums.size() - 1, k - 1);
        }
    };

**原题链接：**[215. 数组中的第K个最大元素][215. _K]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/94d50e8961c541aabbc3e520c6b0cb7d.png
[215. _K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/60d29aae5a044d86aa20ca8e8216d732.png