LeetCode刷题---215. 数组中的第K个最大元素（快速选择）

• 💌 所属专栏：【LeetCode题解（持续更新中）】

• 😀 作  者：我是夜阑的狗🐶

• 🚀 个人简介：一个正在努力学技术的码仔，专注基础和实战分享 ，欢迎咨询！

• 💖 欢迎大家：这里是CSDN，我总结知识的地方，喜欢的话请三连，有问题请私信 😘 😘 😘
  
  

您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！🤩 🤩 🤩

---

前言

  大家好，又见面了，我是夜阑的狗，本文是专栏【LeetCode题解】专栏的第7篇文章，主要讲解是LeetCode215. 数组中的第K个最大元素（双指针，快速选择）。
  专栏地址：【LeetCode题解（持续更新中）】， 此专栏是我是夜阑的狗对LeetCode问题的讲解，希望能够加深自己的印象，以及帮助到其他的小伙伴😉😉。
  如果文章有什么需要改进的地方还请大佬不吝赐教👏👏。

---

一、编程题：215. 数组中的第K个最大元素（快速选择）

1.题目描述

  给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 LeetCode题目链接。

2.示例1：

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

3.示例2：

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

4.提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

二、解题思路

1.思路

解决方法1（个人想法）：

本题主要考察的是堆排序跟快速排序，但两种排序本人掌握的不好，所以只能再去看这两排序的原理。下面要讲解的快速选择算法是在快速排序上得来，至于堆排序待后续补充（还没理解透）；

解决方法2（快速选择）：

• Step1.首先设定一个分界值，通过与该分界值将数组分成左右两部分；
• Step2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值，而右边部分中各元素都大于或等于分界值；
• Step3.然后就能得到当前分界值所在位置，注意这里分界值的位置是已经排序好的，不会再移动。所以可以通过判断第K大（length-k）位置落在分界值的那个区间，来决定对哪边进行递归处理即可
• Step4.重复上述过程，可以看出，这是一个递归定义。通过递归处理第k大所处的区间就能得到该值。

快速排序切分原理：
把一个数组切分成两个子数组的基本思想：

• Step1.找一个基准值，用两个指针分别指向数组的头部和尾部；
• Step2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
• Step3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
• Step4.交换当前左边指针位置和右边指针位置的元素；
• Step5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

---

三、代码实现

每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一（快速选择）：

class Solution {
    int partition(int[] nums, int left, int right, int k){
        //递归结束条件
        if(left == right) return nums[k];
        
        int key = nums[left]; //作为划分数组的基值
        int arrayleft = left; // 指向当前基值的位置
        int arrayright = right+1; //指向右边后一个元素
        while(arrayleft < arrayright){
            //比x小的数放在左边 //先从右往左扫描，找到一个比基准值小的元素
            while(nums[++arrayleft] < key) if(arrayleft == right) break; 
            //比x大的数放在右边 //再从左往右扫描，找一个比基准值大的元素
            while(nums[--arrayright] > key) if(arrayleft == left) break;;
            if(arrayleft < arrayright) swap(nums, arrayleft, arrayright);
        }
        //arrayright为基值的位置
        swap(nums, left,arrayright);
        if(k == arrayright) return nums[k];
        else if(k < arrayright) return partition(nums, left, arrayright-1, k);
        else return partition(nums, arrayright+1, right, k);
    }

    void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public int findKthLargest(int[] nums, int k) {
        int num_length = nums.length;
        return partition(nums, 0, num_length-1, num_length-k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

提交结果：

---

总结

以上就是今天要讲的内容，快速排序算是比较常见的算法了，但过段时间不用的话就会忘的特别快，感觉是没理解透，至于堆排序是我想不到了，只能说平时用到这些排序算法都比较少，以至于适用于什么场景都不清楚，快速选择是看了三叶姐想法之后自己理了一边快速排序写了出来的，其印象比较深刻，所以就赶紧记录一下这个方法，开阔一下思路。

感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹

也欢迎你，关注我。👍 👍 👍

原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

更多专栏订阅:

• 😀 LeetCode题解（持续更新中）
• 🚝 Java Web项目构建过程
• 💛 数字图像处理
• ⚽ JavaScript随手笔记
• 🤩 大数据学习笔记（华为云）
• 🦄 程序错误解决方法（建议收藏）
• 🚀 软件安装教程

订阅更多，你们将会看到更多的优质内容！！