What is the time complexity of Quickselect for the kth largest element?

Quickselect has an average time complexity of O(n) but can degrade to O(n^2) in the worst case, depending on the choice of pivot.

How do you handle edge cases like arrays with duplicates?

Edge cases with duplicates are handled by considering the array in its entirety. The kth largest element will be determined by the total occurrences, not distinct elements.

Can the kth largest element be negative?

Yes, the kth largest element can be negative if the array contains negative numbers. The solution approaches work with negative values the same way they work with positive ones.

Is the heap-based approach faster than Quickselect?

The heap-based approach has a time complexity of O(n log k), which can be faster than Quickselect when k is small relative to the array size, but Quickselect generally has a better average time complexity of O(n).

When is sorting the array a viable approach?

Sorting the array is a simple approach with a time complexity of O(n log n), but it should be avoided when you need a more efficient solution, especially with larger arrays where Quickselect or heaps are preferred.

#215

Medium

auto_awesome堆

LeetCode 题解工作台

数组中的第K个最大元素

给定整数数组 nums 和整数 k ，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。示例 1: 输入: [3,2,1,5,6,4], k = 2 输出: 5 示例 2…

数组分治排序堆（优先队列）快速选择

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

lightbulb

解题思路

方法一：快速选择

快速选择算法是一种在未排序的数组中查找第 k 个最大元素或最小元素的算法。它的基本思想是每次选择一个基准元素，将数组分为两部分，一部分的元素都比基准元素小，另一部分的元素都比基准元素大，然后根据基准元素的位置，决定继续在左边还是右边查找，直到找到第 k 个最大元素。

时间复杂度 $O(n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

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

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(l: int, r: int) -> int:
            if l == r:
                return nums[l]
            i, j = l - 1, r + 1
            x = nums[(l + r) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, r)
            return quick_sort(l, j)

        n = len(nums)
        k = n - k
        return quick_sort(0, n - 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate quickly identify that sorting the array is not the most optimal approach for large arrays?
question_mark
Can the candidate explain the time complexity trade-offs between Quickselect, heaps, and sorting in terms of real-world performance?
question_mark
Does the candidate demonstrate an understanding of how to optimize space complexity when working with heaps or Quickselect?

warning

常见陷阱

外企场景

error
Using a naive sorting approach without considering the more efficient heap or Quickselect methods.
error
Failing to account for the worst-case time complexity of Quickselect and suggesting it as a one-size-fits-all solution.
error
Not recognizing that the kth largest element is not necessarily the kth distinct element, leading to misunderstandings about the problem requirements.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding the kth smallest element in the array instead of the kth largest, which is just a slight modification of the same approach.
arrow_right_alt
Implementing a version where you return the kth largest element in a dynamically changing array, where elements can be added or removed.
arrow_right_alt
Optimizing for memory space when handling very large arrays by considering different heap or Quickselect variants.

help

常见问题

外企场景

继续练习

#347 前 K 个高频元素 #973 最接近原点的 K 个点 #324 摆动排序 II