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

Question

Accepted Answer

可以使用多种方法来找出数组中第 k 大的元素。一种简单的方法是先对数组进行排序，然后取排序后数组的第 k 个元素。排序可以使用 Python 的内置函数 sorted()，时间复杂度为 O(n log n)。以下是代码示例：
python
def findKthLargest(nums, k):
    nums.sort(reverse=True)
    return nums[k - 1]

另一种更高效的方法是使用快速选择算法。快速选择算法是基于快速排序的思想，每次选择一个基准元素，将数组分为两部分，根据基准元素的位置和 k 的大小关系，决定在左半部分或右半部分继续查找。平均时间复杂度为 O(n)，最坏情况下为 O(n^2)。以下是快速选择算法的代码示例：
python
import random

def partition(nums, left, right):
    pivot_index = random.randint(left, right)
    pivot = nums[pivot_index]
    nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
    i = left
    for j in range(left, right):
        if nums[j] >= pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[right] = nums[right], nums[i]
    return i

def quickSelect(nums, left, right, k):
    if left == right:
        return nums[left]
    pivot_index = partition(nums, left, right)
    if pivot_index == k - 1:
        return nums[pivot_index]
    elif pivot_index > k - 1:
        return quickSelect(nums, left, pivot_index - 1, k)
    else:
        return quickSelect(nums, pivot_index + 1, right, k)

def findKthLargest(nums, k):
    return quickSelect(nums, 0, len(nums) - 1, k)

使用快速选择算法可以在平均情况下更高效地找到第 k 大的元素。