047. 编写一个函数，找出数组中的第K大元素

在 Python 中，可以通过多种方法找出数组中的第 K 大元素。

方法 1：使用排序

通过将数组排序，然后直接访问第 K 大的元素。这种方法简单直观，但排序的时间复杂度为 O(nlogn)。

def find_kth_largest_sort(arr, k):
    """
    使用排序找出数组中的第 K 大元素。

    参数:
        arr (list): 输入数组。
        k (int): 第 K 大的元素。

    返回:
        int: 数组中的第 K 大元素。
    """
    sorted_arr = sorted(arr, reverse=True)  # 降序排序
    return sorted_arr[k - 1]  # 返回第 K 大的元素

# 测试代码
arr = [3, 2, 1, 5, 6, 4]
k = 2
print(f"数组中的第 {k} 大元素是：", find_kth_largest_sort(arr, k))

方法 2：使用堆

通过使用堆（优先队列），可以在 O(nlogk) 的时间复杂度内找出第 K 大的元素。Python 的 heapq 模块提供了堆操作的功能。

import heapq

def find_kth_largest_heap(arr, k):
    """
    使用堆找出数组中的第 K 大元素。

    参数:
        arr (list): 输入数组。
        k (int): 第 K 大的元素。

    返回:
        int: 数组中的第 K 大元素。
    """
    min_heap = []  # 使用最小堆
    for num in arr:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)  # 如果堆中元素少于 k 个，直接加入堆
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)  # 如果当前元素大于堆顶元素，替换堆顶
    return min_heap[0]  # 堆顶元素即为第 K 大的元素

# 测试代码
arr = [3, 2, 1, 5, 6, 4]
k = 2
print(f"数组中的第 {k} 大元素是：", find_kth_largest_heap(arr, k))

方法 3：使用快速选择算法

快速选择算法是快速排序的一个变种，可以在平均 O(n) 的时间复杂度内找出第 K 大的元素。以下是实现代码：

def partition(arr, low, high):
    """
    分区函数，将数组分为小于基准和大于基准的两部分。

    参数:
        arr (list): 输入数组。
        low (int): 当前排序区间的起始索引。
        high (int): 当前排序区间的结束索引。

    返回:
        int: 分区点的索引。
    """
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1  # 小于基准的元素的索引

    for j in range(low, high):
        if arr[j] >= pivot:  # 从大到小排序
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # 交换元素

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 将基准放到中间
    return i + 1

def quick_select(arr, low, high, k):
    """
    快速选择算法，找出数组中的第 K 大元素。

    参数:
        arr (list): 输入数组。
        low (int): 当前排序区间的起始索引。
        high (int): 当前排序区间的结束索引。
        k (int): 第 K 大的元素。

    返回:
        int: 数组中的第 K 大元素。
    """
    if low == high:
        return arr[low]

    pivot_index = partition(arr, low, high)  # 找到分区点
    if k == pivot_index:
        return arr[k]
    elif k < pivot_index:
        return quick_select(arr, low, pivot_index - 1, k)  # 在左半部分查找
    else:
        return quick_select(arr, pivot_index + 1, high, k)  # 在右半部分查找

def find_kth_largest_quickselect(arr, k):
    """
    使用快速选择算法找出数组中的第 K 大元素。

    参数:
        arr (list): 输入数组。
        k (int): 第 K 大的元素。

    返回:
        int: 数组中的第 K 大元素。
    """
    return quick_select(arr, 0, len(arr) - 1, k - 1)

# 测试代码
arr = [3, 2, 1, 5, 6, 4]
k = 2
print(f"数组中的第 {k} 大元素是：", find_kth_largest_quickselect(arr, k))

测试结果

运行上述代码后，输出如下：

数组中的第 2 大元素是： 5

代码解释

排序方法：使用 sorted(arr, reverse=True) 对数组进行降序排序，然后直接访问第 K 大的元素。
堆方法：使用最小堆，保持堆的大小为 K。如果当前元素大于堆顶元素，替换堆顶元素。最终堆顶元素即为第 K 大的元素。
快速选择方法：使用快速排序的分区思想，递归地找到第 K 大的元素。通过分区函数将数组分为两部分，根据分区点的位置决定在左半部分还是右半部分继续查找。

注意事项

性能：

排序方法的时间复杂度为 O(nlogn)。
堆方法的时间复杂度为 O(nlogk)。
快速选择方法的平均时间复杂度为 O(n)，但在最坏情况下为 O(n2)。

适用场景：

如果对性能要求不高，排序方法是最简单的实现方式。
如果需要高效处理大数据集，堆方法和快速选择方法更为合适。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)