博客

LeetCode对应题目：

215. Kth Largest Element in an Array (Medium)

题目描述：找到第 k 大的元素。

解题思路1：sort排序方法

时间复杂度 O(NlogN)，空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

解题思路2：堆排序，使用优先队列存储前k个最大元素

时间复杂度 O(NlogK)，空间复杂度 O(K)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(); 
    for (int val : nums) {
        pq.add(val);
        if (pq.size() > k) 
            pq.poll();
    }
    return pq.peek();
}

解题思路3：快速排序，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找，从而降低平均时间复杂度。

时间复杂度 O(N)，空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) {
        k = nums.length-k;
        int l = 0,h = nums.length-1;
        while(l<h){
            int position = partition(nums,l,h);
            if(position == k)
                return nums[position];
            else if(position>k)
                h = position-1;
            else
                l = position+1;
        }
        return nums[k];
    }
    public int partition(int[] nums,int l,int h){
        int i = l+1,j = h;
        while(true){
            while(i<h&&nums[i]<nums[l])
                i++;
            while(j>l&&nums[j]>nums[l])
                j--;
            if(i>=j)
                break;
            swap(nums,i++,j--);
        }
        swap(nums,l,j);
        return j;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }