题解 | #寻找第K大#

寻找第K大

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

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

思路：

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

快速排序中，每次都是取出一个数值，找到这个数值在数值中的正确位置索引，所以我们可以写一个函数专门实现这个功能，即每次都能够找到数组中一个元素的正确位置索引并返回，利用该索引与k-1进行判断（因为下标从0开始，所以第k大元素的下标应该为k-1）;
二分查找中，每次都是判断中间位置的数值与所要查找的目标数值是否相等，如果不相等，那么判断这个数值与目标数值的大小，如果大于目标数值，说明我们需要往这个数值的左边继续查找目标数值，否则往右边查找目标数值；
按照二分查找的思想，如果我们将当前元素的索引与k-1进行比较，如果小于这个k-1，那么表明我们需要往当前元素的右边继续查找。例如当前元素的正确索引是2，但是我们要查找第3大元素，因为数组是降序排列的，所以我们就需要往当前元素的右边继续查找，此时就可以根据二分查找设置对应的递归条件（例如find_k(arr, index + 1, right ,k)，将index看成二分查找中那个中间索引，下面同理）

反之，如果返回的当前元素的正确索引大于这个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;
 }
}