题解 | #利用快排思想求出第K大元素#

利用快排思想求出第K大元素————

1. 利用到的快排思想：选定一个数组元素作为基准，一次快排的结果是（降序）：该基准左侧元素全部大于基准，该基准右侧元素全部小于基准，然后分别对左侧和右侧元素执行相同操作（递归）
2. 结合本题要求：求出第K大元素。假设一次快排结束后的基准下标为mid,基准值为nums[mid],则其前面有mid个元素的值比该基准的值大，因此该基准是第mid+1大的元素,
   即
   (1) 若mid+1==K,则求得第K大元素为nums[mid];
   (2) 若mid+1>K,则第K大的元素在mid左侧，递归左侧元素；
   (3) 若mid+1<K，则第K大的元素在mid右侧，递归右侧元素；

   import java.util.*;
   public class Solution {
    int k;
    public int findKth(int[] a, int n, int K) {
        // write code here
        this.k = K;
        int ans = quickSortFindKth(a,0,n-1);
        return ans;
    }
    public int quickSortFindKth(int[] nums,int left,int right){
        if(left<right){
            int mid = getMid(nums,left,right);
            //对递归的条件作了限制
            if(mid+1==k)
                return nums[mid];
            if(mid+1>k)
                return quickSortFindKth(nums,left,mid-1);
            if(mid+1<k)
                return quickSortFindKth(nums,mid+1,right);
        }
        //此时的中间值即为目标left==right
        return nums[left];
    }
    //求一次快排后基准的下标的代码没有更改（降序）
    public int getMid(int[] nums,int left,int right){
        int pivot = nums[left];
        while(left<right){
            while(left<right&&nums[right]<=pivot){
                right--;
            }
            nums[left] = nums[right];
            while(left<right&&nums[left]>=pivot){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
   

}
```