【练习Day17】寻找第 K 大

链接：寻找第K大_牛客题霸_牛客网

方法：快排+二分查找（推荐使用）

知识点：分治

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

本题需要使用快速排序的思想，快速排序：每次移动，可以找到一个标杆元素，然后将大于它的移到左边，小于它的移到右边，由此整个数组划分成为两部分，然后分别对左边和右边使用同样的方法进行排序，不断划分左右子段，直到整个数组有序。这也是分治的思想，将数组分化成为子段，分而治之。

放到这道题中，如果标杆元素左边刚好有 k−1 个比它大的，那么该元素就是第 k 大：

//若从0开始，刚好是第K个点，则找到
if(K == j + 1)  
    return a[p];

如果它左边的元素比 k−1少，说明第 k 大在其右边，直接二分法进入右边，不用管标杆元素左边:

if(j + 1 < k)
    return partition(a, j + 1, high, k);

同理如果它右边的元素比 k−1 少，那第 k 大在其左边，右边不用管。

return partition(a, low, j - 1, k);

具体做法：

• step 1：进行一次快排，大元素在左，小元素在右，得到的标杆j点.在此之前要使用随机数获取标杆元素，防止数据分布导致每次划分不能均衡。
• step 2：如果 j + 1 = k ，那么j点就是第K大。
• step 3：如果 j + 1 > k，则第k大的元素在左半段，更新high = j - 1，执行step 1。
• step 4：如果 j + 1 < k，则第k大的元素在右半段，更新low = j + 1, 再执行step 1.

import java.util.*;
public class Solution {//交换函数Random r = new Random();public static void swap(int arr[], int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}public int partition(int[] a, int low, int high, int k){//随机快排划分int x = Math.abs(r.nextInt()) % (high - low + 1) + low;swap(a, low, x);int v = a[low];int i = low + 1;int j = high;while(true){//小于标杆的在右while(j >= low + 1 && a[j] < v) j--;//大于标杆的在左while(i <= high && a[i] > v) i++;if(i > j) break;swap(a, i, j);i++;j--;}swap(a, low, j);//从0开始，所以为第j+1大if(j + 1 == k)return a[j];//继续划分else if(j + 1 < k)return partition(a, j + 1, high, k);elsereturn partition(a, low, j - 1, k);}public int findKth(int[] a, int n, int K) {return partition(a, 0, n - 1, K);}
}

复杂度分析：

• 时间复杂度：O(n)，利用二分法缩短了时间——T(2/N)+T(N/4)+T(N/8)+……=T(N)
• 空间复杂度：O(n)，递归栈最大深度