Kth Largest Element in an Array
Kth Largest Element in an Array 给定一个无序的数组,找出第K大的元素,假定k一直有效,1 ≤ k ≤ array's length。 例如给定:nuts = , k = 2 返回 5
如果我们用Arrays的sort方法将数组排序,然后输出nums就是第k大的元素。代码如下:
public class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
如果我们在面试中遇到这个问题,这显然不是面试者想考察的地方。我们可以用快排是解决这个问题,在数组中取一个元素作为pivot,第一次循环后,查看pivot的位置,通过它的位置来递归找到第k大的元素。代码如下:
public class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSort(0, nums.length - 1, nums, k);
}
public int quickSort(int l, int r, int[] nums, int k) {
int i = l, j = r, pivot = nums[l];
while(i < j) {
while(i < j && nums[j] >= pivot)
j --;
if(i < j)
nums[i++] = nums[j];
while(i < j && nums[i] <= pivot)
i ++;
if(i < j)
nums[j--] = nums[i];
}
nums[i] = pivot;
if(nums.length - i == k) return nums[i];
if(nums.length - i < k) return quickSort(l, i - 1, nums, k);
return quickSort(i + 1, r, nums, k);
}
}