题解 | #寻找第K大#快速排序

寻找第K大

http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        int k = n -K;
        int lo = 0, hi = n-1;
        while( lo < hi){
            int p = quickSort(a,lo,hi);
            if( p > k){
                hi = p-1;
            }else if( p < k){
                lo = p+1;
            }else{
                break;
            }
        }
        return a[k];
    }
    public int quickSort(int[] arr,int i,int j){
        int lo = i,hi =j;
        int key = arr[i];
        while(lo < hi){
            while(lo < hi && key <= arr[hi]){
                hi --;
            }
            while(lo <hi && key >= arr[lo]){
                lo ++;
            }
            exchange( arr, lo, hi);
        }
        exchange( arr, i, lo);
        return lo;
    }
    public void exchange( int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-21 17:16
科大讯飞 算法工程师 28.0k*14.0, 百分之三十是绩效,惯例只发0.9
点赞 评论 收藏
分享
威猛的小饼干正在背八股:挂到根本不想整理
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务