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

简介: 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);
    }
}

提交结果:


总结

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

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

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

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


相关文章
|
4天前
|
存储
力扣 合并两个有序数列||移除元素
力扣 合并两个有序数列||移除元素
10 0
|
6天前
|
算法 Java 索引
【Java 刷题记录】双指针(下)
【Java 刷题记录】双指针
26 0
|
6天前
|
算法 Java 容器
【Java 刷题记录】双指针(上)
【Java 刷题记录】双指针
22 0
|
6天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
6天前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
13 2
|
6天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
12 0
|
6天前
leetcode代码记录(下一个更大元素 II
leetcode代码记录(下一个更大元素 II
9 0
|
6天前
|
索引
leetcode代码记录(下一个更大元素 I
leetcode代码记录(下一个更大元素 I
8 0
|
6天前
leetcode代码记录(两个数组的交集
leetcode代码记录(两个数组的交集
9 1
|
6天前
leetcode代码记录(最大子数组和
leetcode代码记录(最大子数组和
12 2

热门文章

最新文章