题解 | #寻找第K大#

一个快排+二分搞了我一天的时间，思路是知道的但对于快排的很多细节没有掌握到位，导致踩了很多坑
先看一下快排

public class Quickmethod {
    public static void sort (Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    private static void sort(Comparable [] a,int lo,int hi){
        //初始化两个指针，第二个索引以及最后一个索引
        int left = lo+1;
        int right = hi;
        int mid = 0;

        //递归边界
        if(lo>=hi){
            return;
        }
        //指针移动寻找大于首元素的值和小于首元素的值（循环操作至两个指针相遇）
        while(true) {//关键点

            //二号指针找到小于首元素的元素时停止
            while(a[right].compareTo(a[lo])>0){  //二号指针需要先移动
                right--;
                if (right==lo){
                     break;//已经扫描到最左边了，无需继续扫描
                    }
            }
            //一号指针找到大于首元素的元素时停止
            while(a[left].compareTo(a[lo])<0){
                left++;
                if (left==hi){
                    break;//已经扫描到了最右边了，无需继续扫描
                    }
            }

            //一号二号指针元素交换
            if(right>left){
                exch(a,left,right);
            }else{
                //扫描完所有元素
                break;
            }
        }

        //两个指针相遇初索引设定成right，或者right指针直接走到尽头未相遇；并将首元素和此处的元素进行交换
        exch(a,lo,right);// right分界点赋值

        //递归
        sort(a,lo,right-1); //注意-1
        sort(a,right+1,hi); //注意+1
    }


    private static void exch(Comparable []a,int i,int j){
        Comparable temp;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;

    }
}

快排清楚了，那么也就容易了

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quicksearch(a,0,n-1,K ,n);

    }
    public int quicksearch(int[] a, int first, int last, int k ,int length){
        int temp1 = first+1;
        int temp2 = last;

        if(first>=last){ //递归边界
            if((length - first)==k){
                return a[first];
            }
            return -1;
        }
        while(true){ //关键
            //寻找a[i]小于首元素的 位置 用于交换
            while(a[temp2]>=a[first]){
                temp2--;
                if(temp2<=first){
                    break;
                }
            }
            //寻找a[i]大于首元素的 位置 用于交换
            while(a[temp1]<=a[first]){
                temp1++;
                if(temp1>=last){
                    break;
                }
            }

            if(temp1<temp2){
                exch(a,temp1,temp2);
            }else { //关键
                break;
            }

        }

        exch(a,temp2,first);

       //二分思想
        if((length - temp2)>k){
            return quicksearch(a,temp2+1,last,k,length);
        }
        if((length - temp2)==k){
            return a[temp2];
        }
        if((length - temp2)<k){

            return quicksearch(a,first,temp2-1,k,length);
        }

        return -1;
    }
    public void exch(int[] a, int temp1, int temp2){
        int s = a[temp1];
        a[temp1] = a[temp2];
        a[temp2] = s;
    }
}