牛客网
寻找第K大【中等】
题目链接：寻找第K大
题目内容：有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
最佳思路：快排+二分+随机基准点。在快排的过程中不断的找到对应的基准点，然后以这个基准点比较k（基准点的左边是>该基准点的，这样我们才能将基准点的索引与第k大的索引来进行比较）
思路：快排+二分+随机基准点
复杂度分析：
时间复杂度：O(n.logn)
空间复杂度：O(n)
一个探索思路的过程：
import java.util.*; public class Solution { private static int res; Private static Random random = new Ramdom(); public int findKth(int[] a, int n, int K) { quickSort(a, 0, n - 1, K); return res; } public void quickSort(int[] a, int l, int r, int K) { if (l > r) { return; } int mid = partition(a, l, r); //看这个基准点与K的位置是否相符 if (mid + 1 == K) { res = a[mid]; }else if (mid + 1 < K) { quickSort(a, mid + 1, r, K); }else { quickSort(a, 0, mid - 1, K); } } public int partition(int[] a, int l, int r) { int x = Math.abs(random.nextInt()) % (r - l + 1) + l; swap(a, l, x); int j = l; for (int i = l + 1; i <= r; i++) { if (a[i] >= a[l]) { j++; swap(a, i, j); } } //交换基准点 swap(a, l, j); return j; } public void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
不同的分块思路：
//方式一： public int partition(int[] a, int l, int r) { int x = Math.abs(random.nextInt()) % (r - l + 1) + l; swap(a, l, x); int j = l; for (int i = l + 1; i <= r; i++) { if (a[i] >= a[l]) { j++; swap(a, i, j); } } //交换基准点 swap(a, l, j); return j; } //方式二： public int partition(int[] a, int l, int r) { int v = a[l]; int i = l + 1; int j = r; while (true) { //目标找到小于基准值的 while (i <= r && a[i] > v ) { i++; } //目标找到大于基准值的 //注意：这里j>=l+1 while (j >= l + 1 && a[j] < v) { j--; } if (i > j) { break; } swap(a, i, j); i++; j--; } //交换基准点 swap(a, l, j); return j; }
