题目
第k大元素
在数组中找到第k大的元素
样例
给出数组[9,3,2,4,8]，第三大的元素是4
给出数组 [1,2,3,4,5]，第一大的元素是5，第二大的元素是4，第三大的元素是3，以此类推
注意
你可以交换数组中的元素的位置
挑战
要求时间复杂度为O(n），空间复杂度为O(1）
解题
理论快速排序的思想，每次都减半，这个时间复杂度也是O(N)，至于为什么就不知道了
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
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);
}
}
};
Python
class Solution:
# @param k & A a integer and an array
# @return ans a integer
def kthLargestElement(self, k, A):
return self.quickSort(A,0,len(A)-1,k) def quickSort(self,nums,left,right,k):
i = left
j = right
tmp = nums[i]
while i<j:
while i<j and tmp>=nums[j]:
j -= 1
if i<j:
nums[i] = nums[j]
i += 1
while i<j and tmp< nums[i]:
i += 1
if i<j:
nums[j] = nums[i]
j -= 1
if i == k-1:
return tmp
elif i< k-1:
return self.quickSort(nums,i+1,right,k)
else:
return self.quickSort(nums,left,i-1,k)
Python Code