题解 | #寻找第K大#

快速排序跟二分查找解题

快速排序是确定一个枢轴，然后将数组中大于枢轴的元素移动到枢轴左边，将数组中小于枢轴的元素移动到枢轴右边，然后在递归处理枢轴左右两边的元素。

一般确定第一个元素为枢轴，然后用双指针法，一个指针从左到右遍历找小于枢轴的元素，另一个指针从右到左遍历找大于枢轴的元素，然后再交换这两个元素，两个指针相遇后就是枢轴的位置。

如果枢轴的位置就是第K个元素，则第K大元素就是枢轴，如果枢轴的位置大于K，说明K在枢轴的左边，递归对枢轴左边的元素进行快速排序，如果枢轴的位置小于K，说明K在枢轴的右边，递归对枢轴右边的元素进行快速排序。

参考

https://blog.nowcoder.net/n/1936bf8e02964bde9022d653aec858a2?f=comment

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public int quickSort(int[] a, int low, int high, int k) {
        
        int v = a[low];  // 取第一个值为枢轴，但有可能会失效，随机选取比较好。
        int i = low + 1;
        int j = high;

        while(true) {
            // 从右边开始找大于枢轴的值，i和j相等时也可进入循环
            while(j >= i && a[j] < v) {
                j--;
            }
            // 从左边开始找小于枢轴的值，i和j相等时也可进入循环
            while(i <= j && a[i] > v) {
                i++;
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
            i++;
            j--;
        }
        swap(a, low, j);  // 将枢轴的值放到i和j相等的地方
        if(j + 1 == k) {
            return a[j];  // 此时枢轴就是第k大的值
        }
        else if(j + 1 < k) {
            return quickSort(a, j + 1, high, k);  // 此时第k大的值在枢轴右边
        }
        else {
            return quickSort(a, low, j - 1, k);  // 此时第k大的值在枢轴左边
        }
    }
    public int findKth (int[] a, int n, int K) {
        // write code here
        return quickSort(a, 0, n-1, K);
    }
}