1 题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 暴力破解

先将数组中所有元素进行排序，如果按照顺序排序，则输出第nums.length-K个元素，如果是按照逆序排序，则输出第K-1个元素。
这里使用快速排序，因为时间复杂度是O(nlogn)。

public class FindKth {public int findKth(int[] a, int n, int K) {// write code herequickSort(a, 0, n - 1);return a[a.length-K];}private void quickSort(int[] a, int start, int end) {//= partition(a,start,end);//从大到小排序  每次执行完partition之后，能确定数组中第pIndex大的数，if (start>=end)return;int pIndex = partition(a,start,end);quickSort(a,start,pIndex-1);quickSort(a,pIndex+1,end);}private int partition(int[] a, int start, int end) {int p = a[start];int mark = start;for (int i = start; i <= end; i++) {if (a[i] < p) {mark++;int t = a[i];a[i] = a[mark];a[mark] = t;}}a[start] = a[mark];a[mark] = p;return mark;}public static void main(String[] args) {int []a={1,6,6,4,5};int k = 3;FindKth findKth = new FindKth();int res = findKth.findKth(a, a.length, k);System.out.println(res);}
}

3 快速排序思路

利用快速排序的思想，这里的基准元素取第一个，每次partition()执行完之后，总能确定数组中第i个的位置，按照降序顺序进行排序的话，则每次能确定第i大的元素，然后判断当前的i与 K的大小即可：

• 如果i>K：则说明当前的元素偏小（降序排序），应该到数组的左边进行查找
• 如果i<K：则说明当前的元素偏大，应该到数组的右边进行查找
• 如果i==K：则说明找到了当前元素，返回nums[i]

public class FindKthWithQuickSort {public int findKth(int[] a, int n, int K) {return quickSort(a, 0, n - 1, K);}private int quickSort(int[] a, int start, int end, int K) {int l = start, r = end;int p = a[start];while (l < r) { //降序排序while (l < r && a[r] < p) r--;a[l] = a[r];while (l < r && a[l] >= p) l++;a[r] = a[l];}a[l] = p;if (l == K - 1)return a[l];else if (l > K - 1) { //表示该数在数组左边return quickSort(a, start, l - 1, K);} else { //表示该数在数组右边return quickSort(a, l + 1, end, K);}}public static void main(String[] args) {int[] a = {1, 6, 6, 4, 5};int k = 3;FindKthWithQuickSort findKthWithQuickSort = new FindKthWithQuickSort();int res = findKthWithQuickSort.findKth(a, a.length, k);System.out.println(res);}
}

4 大顶堆思路

该方法比快速排序的思路要更快，

刚开始建立一个大顶堆，然后每次删除一个元素，即堆顶的元素，删除K次之后的堆顶元素便是第K大的元素。

public class FindKthWithHeap {public int sort(int []nums,int K){for (int i = nums.length/2; i >=0 ; i--) {downAdjust(nums,i,nums.length);}int index = 0;for (int i = nums.length-1; i >0 ; i--) {if (index++>=K-1)break;int t = nums[i];nums[i]=nums[0];nums[0]=t;downAdjust(nums,0,i);}return nums[0];}/*** @param a: array* @param i: root index*/private void downAdjust(int[] a, int i,int n) {int childIndex = 2 * i + 1;//left child indexint tem = a[i];while (childIndex < n) {//when left child less than right child, left->rightif (childIndex + 1 < n && a[childIndex] < a[childIndex + 1]) {childIndex++;}if (tem > a[childIndex]) //大顶堆break;a[i] = a[childIndex];i = childIndex; //向下继续查找childIndex = 2 * childIndex + 1;}a[i] = tem;}public static void main(String[] args) {int[] a = {3,2,3,1,2,4,5,5,6};FindKthWithHeap findKthWithHeap = new FindKthWithHeap();int res = findKthWithHeap.sort(a,4);System.out.println(res);}
}