题目

描述

在数组中找到第k大的元素

样例

给出数组 [9,3,2,4,8]，第三大的元素是 4

给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

解答

思路

1. 快速排序
2. 返回倒数第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;
    }
};