https://leetcode.com/problems/kth-largest-element-in-an-array/description/
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
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
这题只要懂得快速排序的partition函数就行了。快速排序的partition函数执行一次是log(n)时间，一次执行完了会返回pivot在数组中的正确位置，那么这个位置+1如果正好是k，就是我们要找的结果了。
不过这个时间复杂度有点难判断啊，首先肯定是高于n*log(n)的，因为每次搜索都丢掉一半，比quicksort快。网上说是O(n)。
public int findKthLargest(int[] nums, int k) {
if (k < 1 || k > nums.length || nums == null) return Integer.MAX_VALUE;
return helper(nums, 0, nums.length - 1, k);
}
//要注意index需要+1
private int helper(int[] nums, int low, int high, int k) {
int index = partition(nums, low, high);
if (index + 1 == k) {
return nums[index];
} else if (index + 1 < k) {
return helper(nums, index + 1, high, k);
} else {
return helper(nums, low, index - 1, k);
}
}
private int partition(int[] nums, int low, int high) {
int i = low, pivot = nums[high];
for (int j = low; j < high; j++) {
if (nums[j] > pivot) {
swap(i, j, nums);
i++;
}
}
swap(i, high, nums);
return i;
}
private void swap(int a, int b, int[] arr) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
