题目
在数组中找到第k大的元素
样例
给出数组[9,3,2,4,8],第三大的元素是4
给出数组 [1,2,3,4,5],第一大的元素是5,第二大的元素是4,第三大的元素是3,以此类推
注意
你可以交换数组中的元素的位置
挑战
要求时间复杂度为O(n),空间复杂度为O(1)
代码
public int kthLargestElement(int k, int[] nums) {
// write your code here
return quickSort(nums,0,nums.length-1,k);
}
public int quickSort(int[] nums,int left,int right,int k){
int i = left;
int j = right;
int tmp = nums[i];
while(i<j){
while(i<j && tmp>=nums[j]) j--;
if(i<j){
nums[i]=nums[j];
i++;
}
while(i<j && tmp<nums[i]) i++;
if(i<j){
nums[j]=nums[i];
j--;
}
}
if(i == k -1){
return tmp;
}else if(i< k-1){
return quickSort(nums,i+1,right,k);
}else{
return quickSort(nums,left,i-1,k);
}
}
本文由 Time 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jul 24, 2018 at 05:20 pm