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
Note: You may assume k is always valid, 1 ≤ k ≤ array's length.
题目翻译
找出未排序数组中第k大的元素，注意，第k大是指在排序的顺序的第k大，而非距离第k大的元素。
示例1：
输入：[3,2,1,5,6,4] 以及 k = 2
输出: 5
注意： 你可以假设k永远是有效的，即1 ≤ k ≤ 数组长度
解题方案
标签： Divide and Conquer
思路：
- 这道题有很多解法，利用分治的想法我们的思路如下：
- 随机取输入数组中的一个数x(如数组正中间的数)，遍历数组，将数组中比它小的放入左，比它大的放入右边，记两边的长度为len1与len2
- 若k<len1，则第k大的数肯定在左边，反之在右边。
- 在确定的范围内重复上述操作，当k = len1时，找到第k大的数。
代码：
public class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, k - 1, 0, nums.length - 1);
}
private int quickSelect(int[] arr, int k, int left, int right){
int pivot = arr[(left + right) / 2];
int orgL = left, orgR = right;
while(left <= right){
// 从右向左找到第一个小于枢纽值的数
while(arr[left] > pivot){
left ++;
}
// 从左向右找到第一个大于枢纽值的数
while(arr[right] < pivot){
right --;
}
// 将两个数互换
if(left <= right){
swap(arr, left, right);
left ++;
right --;
}
}
// 最后退出的情况应该是右指针在左指针左边一格
// 这时如果右指针还大于等于k，说明kth在左半边
if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
// 这时如果左指针还小于等于k，说明kth在右半边
if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
return arr[k];
}
private void swap(int[] arr, int idx1, int idx2){
int tmp = arr[idx1] + arr[idx2];
arr[idx1] = tmp - arr[idx1];
arr[idx2] = tmp - arr[idx2];
}
}