给定一个无序数组，找出其中第 k 大的元素。

Question

Accepted Answer

可以采用快速选择算法来解决这个问题。快速选择算法是基于快速排序的思想，但它只需要处理包含第 k 大元素的那一部分数组，从而减少了不必要的排序操作。具体步骤如下：1. 选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。2. 计算基准元素在排序后的数组中的位置，如果该位置等于 k - 1，则基准元素就是第 k 大的元素；如果该位置大于 k - 1，则第 k 大的元素在左边部分，继续在左边部分进行快速选择；如果该位置小于 k - 1，则第 k 大的元素在右边部分，继续在右边部分进行快速选择。以下是 Python 代码实现：
python
def quick_select(nums, k):
    def partition(left, right):
        pivot = nums[right]
        i = left - 1
        for j in range(left, right):
            if nums[j] >= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1], nums[right] = nums[right], nums[i + 1]
        return i + 1
    left, right = 0, len(nums) - 1
    while True:
        pos = partition(left, right)
        if pos == k - 1:
            return nums[pos]
        elif pos > k - 1:
            right = pos - 1
        else:
            left = pos + 1
快速选择算法的平均时间复杂度为 O(n)，最坏情况下为 O(n^2)。