Find thekth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,Given[3,2,1,5,6,4]and k = 2, return 5.
Note:You may assume k is always valid, 1 ≤ k ≤ array’s length.
Credits:Special thanks to@mithmattfor adding this problem and creating all test cases.
算法:
最小堆排序
public class Solution {public int findKthLargest(int[] nums, int k) {int[] b = new int[k];for (int i = 0; i < k; i++) {b[i] = nums[i];}for(int i=b.length/2;i>=0;i–){minHeapSort(b,i,b.length);}for (int i = k; i < nums.length; i++) {if (nums[i] > b[0]) {b[0] = nums[i];minHeapSort(b,0,b.length);}}return b[0];}private void minHeapSort(int[] b,int i, int n) {int tmp = b[i];int child;for (; i * 2 + 1 < n; i = child) {child = i * 2 + 1;if (child < n – 1 && b[child + 1] < b[child]) {child++;}if (tmp > b[child]) {b[i] = b[child];} elsebreak;}b[i] = tmp;}}
,有多少和我一样,坐在不足平米的空间里,