美文网首页算法
LeetCode题解:寻找第K大数

LeetCode题解:寻找第K大数

作者: 搬码人 | 来源:发表于2022-05-22 11:48 被阅读0次

    题目描述

    有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
    给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
    要求:时间复杂度 O(nlogn),空间复杂度 O(1)

    示例

    • 示例1
      输入:[1,3,5,2,2],5,3
      输出:2
    • 示例2
      输入:[10,10,9,9,8,7,5,6,4,3,4,2],12,3
      输出:9
      说明:去重后的第3大是8,但本题要求包含重复的元素,不用去重,所以输出9 。

    方法思路

    典型的快速排序
    1、进行一次快排,大元素在左,小元素在右,得到的中轴p点;
    2、如果 p - low + 1 = k ,那么p点就是第K大。
    3、如果 p - low + 1 > k,则第k大的元素在左半段,更新high = p - 1,执行step 1。
    4、如果 p - low + 1 < k,则第k大的元素在右半段,更新low = p + 1, 且 k = k - (p - low + 1),排除掉前面部分更大的元素,再执行step 1。

    import java.util.*;
    
    public class Solution {
        //常规的快排划分,但是这次是大数在左
        public int partion(int[] a,int low,int high){
            int temp = a[low];
            while(low<high){
                //小于标杆的在右
                while(low<high && a[high]<=temp){
                    high--;
                }
                if(low==high){
                    break;
                }else{
                    a[low] = a[high];
                }
                //大于标杆的在左
                while(low<high && a[low]>=temp){
                    low++;
                }
                if(low==high){
                    break;
                }else{
                    a[high] = a[low];
                }
            }
            a[low] = temp;
            return low;
        }
        public int quickSort(int[] a,int low,int high,int K){
            //先进行一轮划分,p下标左边的都比它大,下标右边都比它小
            int p  = partion(a,low,high);
            //若p刚好是第K个点,则找到
            if(K == p-low+1){
                return a[p];
            }else if(p-low+1>K){
                //从头到p超过k个数组,则目标在左边
               return quickSort(a,low,p-1,K); 
            }else{
                //否则,在右边,递归右边,但是需要减去左边最大的数字的数量
                return quickSort(a,p+1,high,K-(p-low+1));
            }
        }
        public int findKth(int[] a, int n, int K) {
            // write code here
            return quickSort(a,0,n-1,K);
        }
        
    }
    

    相关文章

      网友评论

        本文标题:LeetCode题解:寻找第K大数

        本文链接:https://www.haomeiwen.com/subject/frskprtx.html