题目
在未排序的数组中找到第 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 ≤ 数组的长度。
思路
- 对数组排序，取索引值为k-1处的值。
时间复杂度是排序算法的时间复杂度：O(nlogn)
虽然这个解法是正确的，但还可以继续优化：我们只需返回第K大的数，没必要对整个数组排序。 - 利用快排Partition思想
Partition后，会把选取的枢纽元素放在排序后的正确位置，其左边是比其大的元素，其右边是比pivot值小的元素。
假设此时枢纽元素位于索引X处：若K>X+1，继续在X右边查找；若K<X+1，继续在X左边查找。
直到K==X+1 ，此时找到nums数组中第K大的数：nums[K-1]。
Java实现
class Solution {
public int findKthLargest(int[] nums, int k) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int j = partition(nums, lo, hi);
if(j+1 < k)
lo = j + 1 ;
else if (j+1 > k)
hi = j - 1;
else
break;
}
return nums[k-1];
}
private void exch(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
private int partition(int nums[] , int l, int r){
int j=l;
int v = nums[l];
for(int i=l+1;i<=r;i++){
if(nums[i]>v)
exch(nums,++j,i);
}
exch(nums,l,j);
return j;
}
}
- 利用最小堆
后面再补
