LC.P215[数组中的第K个最大元素]

方法一：大根堆

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) q.offer(num);
        while (k-- > 1) {
            q.poll();
        }
        return q.peek();
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$

方法二：小根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> a - b);
        for (int i = 0; i < k; ++i) q.offer(nums[i]);
        // 维护一个大小为k的小根堆，堆顶元素即为第k大的数
        for (int i = k; i < nums.length; ++i) {
            if (q.peek() < nums[i]) {
                q.poll();
                q.offer(nums[i]);
            }
        }
        return q.peek();
    }
}
  • 时间复杂度：$O(nlogk)$
  • 空间复杂度：$O(k)$

方法三：快速选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int[] nums;

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        int n = nums.length;
        return quickSelect(0, n - 1, n - k);
    }

    private int quickSelect(int left, int right, int k) {
        if (left == right) return nums[k];
        int x = nums[left + right >> 1], i = left - 1, j = right + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        if (k <= j) return quickSelect(left, j, k);
        else return quickSelect(j + 1, right, k);
    }

    private void swap(int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(logn)$，划分函数的平均递归深度为 $O(logn)$