算法

题目

在数组中找到第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