首页 > 每天刷一道牛客题霸-第6天-寻找第K大
头像
菜鸟也要飞的高
编辑于 2020-12-03 14:27
+ 关注

每天刷一道牛客题霸-第6天-寻找第K大

题目

https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tpId=190&&tqId=35209&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking

import java.util.*;

public class Finder {
    public static int findKth(int[] a, int n, int K) {

        return quickSort(a,0,n-1,K);
        // write code here
    }
    public static int quickSort(int[] a, int start,int end,int K){
        if(a.length > 0 && end > start ){
            int index =  patition(a, start, end,K);
            if (K -1 < index){
                quickSort(a, start, index-1,K);
                return a[K-1];
            }else if (K -1 > index) {
                quickSort(a, index + 1, end, K);
                return a[K-1];
            }else {
                return a[index];
            }

        }
        return -1;
    }
    public static int patition(int[] a, int start , int end ,int K){
        int index  = a[start];
        while (start < end) {
            while (end > start && a[end] <= index) {
                end--;
            }
            a[start] = a[end];
            while (start < end && a[start] >= index) {
                start++;
            }
            a[end] = a[start];
        }
        a[start] = index;
        return start;
    }
}

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐