题目
描述
在数组中找到第k大的元素
样例
给出数组 [9,3,2,4,8]，第三大的元素是 4
给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推
解答
思路
- 快速排序
- 返回倒数第k个元素
代码
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
// write your code here
quickSort(nums,0, nums.length-1);
return nums[nums.length-k];
}
private void quickSort(int[] nums, int start, int end){
if(start > end){
return;
}
int i = start,j = end;
int temp = nums[i];
boolean flag = true;
while(i != j){
while(nums[j]>=temp && i<j) j--;
while(nums[i]<=temp && i<j) i++;
if(i<j) swap(nums,i,j);
}
nums[start]=nums[i];nums[i]=temp;
quickSort(nums, start, i-1);
quickSort(nums, i+1, end);
}
private void swap(int[] nums, int i, int j){
int temp;
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
