题解 | #寻找第K大#

快速排序与二分查找的结合

思路：

注：因为要查找第K大元素，所以数组应该是降序排列的（这样就可以直接通过k-1来获取对应的第K大元素了），因此需要修改快速排序中相应的判断条件

1. 快速排序中，每次都是取出一个数值，找到这个数值在数值中的正确位置索引，所以我们可以写一个函数专门实现这个功能，即每次都能够找到数组中一个元素的正确位置索引并返回，利用该索引与k-1进行判断（因为下标从0开始，所以第k大元素的下标应该为k-1）;

2. 二分查找中，每次都是判断中间位置的数值与所要查找的目标数值是否相等，如果不相等，那么判断这个数值与目标数值的大小，如果大于目标数值，说明我们需要往这个数值的左边继续查找目标数值，否则往右边查找目标数值；

3. 按照二分查找的思想，如果我们将当前元素的索引与k-1进行比较，如果小于这个k-1，那么表明我们需要往当前元素的右边继续查找。例如当前元素的正确索引是2，但是我们要查找第3大元素，因为数组是降序排列的，所以我们就需要往当前元素的右边继续查找，此时就可以根据二分查找设置对应的递归条件（例如find_k(arr, index + 1, right ,k)，将index看成二分查找中那个中间索引，下面同理）

4. 反之，如果返回的当前元素的正确索引大于这个k-1,说明我们需要往当前元素的左边继续查找。例如返回的当前元素的索引是5，但是我们需要查找第3大元素，因为数组是降序排列的，所以此刻我们就需要往当前元素的左边继续查找，此时就可以根据二分查找的思想设置对应的递归条件（例如find_k(arr, left, index - 1, k)）

    import java.util.*;
   
    public class Solution {
        public int findKth(int[] a, int n, int K) {
            // write code here
            // 快速排序和二分查找思想的结合
            int index = find_k(a, 0, n - 1, K);
            return index;
        }
   
    public int find_index(int[] arr, int left, int right) {
        // 该函数的目的是要返回当前这个值在整个数组中的正确索引
        // 也就是说,当前这个值在arr是已经有序的情况下,这个值所处的索引
        // 按照快速排序的思想,每次都是将当前值放在正确的位置上,也就意味着每次都是要找到
        // 当前这个值的正确索引
        // 所以这个函数可以看成是快速排序中的一个小部分,用来找到每个数值的正确索引
   
        // 假设s就是当前数值,现在要通过遍历数组,找到s这个数值在arr数组中的正确位置是在哪儿
        int s = arr[left]; 
   
        while (left < right) {
            // 因为题目是找到第K大的数值,所以我们需要对数组进行降序排列,而快速排序默认是升序排列
            // 所以这里的条件判断与快速排序中的写法相反
            while (left < right && arr[right] <= s) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] >= s) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = s;
        // 最终返回当前值s在数组arr中的正确索引,即当arr已经排好序的情况下,这个s所在的索引
        return left;
    }
   
    public int find_k(int[] arr, int left, int right, int k) {
        // 该函数用于判断所返回的索引与k-1是否相等
        // 如果相等,表明我们已经找到了第k大元素（数组下标从0开始,所以比较的时候k应该-1）
        // 如果不相等,就需要按照二分查找的方式进行递归查找
        // 因为我们每次获取到的索引都是已经通过快排思想找到的正确索引
   
        if (left <= right) {
            int index = find_index(arr, left, right);
            if (index == k -1) {
                return arr[index];
            }else if (index > k - 1) {
                // 如果返回的这个数值索引比k-1要大，说明要找的数值应该处于这个第K大数值的右边
                // 因为每次快排的时候是降序排列的
                // 例如返回的是5，但是我们要找第3大的数值，如果数组是降序排列的话，那么我们
                // 此时就应该往左边找,所以按照二分查找的做法，输入的右边索引为index -1，
                // 这样就能够从左边继续找第K大数值了
                return find_k(arr, left, index - 1, k);
            }else {
                // 如果与上面结果相反，例如返回的数值索引是2，但我们要找第3大数值，
                // 因为数组是降序的，所以此刻第3大数值应该位于索引为2数值的右边
                // 所以按照二分查找的做法，输入的左边索引为index + 1，让我们从右边继续查找第k大数值
                // 直到找到第k大数值为止，即返回的index == k - 1;
                return find_k(arr, index + 1, right ,k);
            }
        }
        return -1;
    }
   }