Leetcode刷题之 【215. 数组中的第K个最大元素】

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 here quickSort(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 index int tem = a[i]; while (childIndex < n) { //when left child less than right child, left->right if (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); } }