215. Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
题意：给一个数组， 求出第 kth 大的数是几。 经典题题之一。 首先最简单的办法就是直接排序，返回 arr.length - k 位置上的那个值。 这样做的复杂度是 nlogn. 还可以维护一个大小为 k 的 heap， 这样做的复杂度为 nlogk。
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (a - b));
for(int i : nums) {
if(pq.isEmpty() || pq.size() < k) pq.add(i);
else if(pq.size() >= k && pq.peek() < i) {
pq.poll();
pq.offer(i);
}
}
return pq.peek();
}
}
然而最快的解法是利用快排的思想。 每次我们都随机选一个数，把小的放置于左侧，大的放置于右侧。 如果排序之后，选中的这个数的 index 刚好和 arr.length - k 相等，那么我们就可以直接返回答案了。 因为每次只需要递归一半进去， 时间复杂度就等于 O(n/2) + O(n/4) + … + O(1), 合起来就是 O(n). 当然这是平摊复杂度，最差的情况 是 O(n^2); 这里面为了减少出错的概率，还是把 func 分开来写。 partition func 中注意 i 一直 track 的是已经满足小于 pivot 的值。
代码
class Solution {
public void swap(int[] arr, int i, int j) {
if(i == j) return;
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
return;
}
public int partition(int[] arr, int i, int j, int p) {
swap(arr, j, p);
int pivot = j, start = i;
j--;
i--;
while(start <= j) {
if(arr[start] < arr[pivot]) {
i++;
swap(arr, i, start);
}
start++;
}
swap(arr, i + 1, pivot);
return i + 1;
}
public int sort(int[] arr, int start, int end, int k) {
if(start == end) return arr[start];
if(start < end) {
Random random_num = new Random();
int p = start + random_num.nextInt(end - start);
int index = partition(arr, start, end, p);
//System.out.println(index);
if(index == k) return arr[k];
if(index < k) {
return sort(arr, index + 1, end, k);
} else {
return sort(arr, start, index - 1, k);
}
}
return -1;
}
public int findKthLargest(int[] nums, int k) {
return sort(nums, 0, nums.length - 1, nums.length - k);
}
}