第k大元素
in 算法 with 0 comment

第k大元素

in 算法 with 0 comment

题目

在数组中找到第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);
    }
}
Responses