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

一、编程题：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);
    }
}

提交结果：

总结

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

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

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

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