Kth Largest Element in an Array,LeetCode,215

题目描述：

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

示例 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 个最大的元素。

代码实现（Python）：

def findKthLargest(nums, k): nums.sort(reverse=True) return nums[k-1]

时间复杂度： O(n log n)，其中 n 是数组的长度。

空间复杂度： O(1)，如果忽略排序算法的额外空间。

2. 堆排序法

使用最小堆来维护前 k 个最大的元素。

代码实现（Python）：

import heapq

def findKthLargest(nums, k): return heapq.nlargest(k, nums)[-1]

或者使用最小堆手动维护：

import heapq

def findKthLargest(nums, k): min_heap = [] for num in nums: if len(min_heap) < k: heapq.heappush(min_heap, num) else: heapq.heappushpop(min_heap, num) return min_heap[0]

时间复杂度： O(n log k)，其中 n 是数组的长度。

空间复杂度： O(k)，用于存储堆。

3. 快速选择法

基于快速排序的分区思想，通过选择一个 pivot 将数组分为两部分，然后判断第 k 个最大的元素在哪个部分。

代码实现（Python）：

def findKthLargest(nums, k): def partition(left, right, pivot_index): pivot_value = nums[pivot_index] nums[pivot_index], nums[right] = nums[right], nums[pivot_index] store_index = left for i in range(left, right): if nums[i] > pivot_value: nums[store_index], nums[i] = nums[i], nums[store_index] store_index += 1 nums[right], nums[store_index] = nums[store_index], nums[right] return store_index

def select(left, right, k_smallest):
    if left == right:
        return nums[left]
    pivot_index = left
    pivot_index = partition(left, right, pivot_index)
    if k_smallest == pivot_index:
        return nums[k_smallest]
    elif k_smallest < pivot_index:
        return select(left, pivot_index - 1, k_smallest)
    else:
        return select(pivot_index + 1, right, k_smallest)

return select(0, len(nums) - 1, k - 1)

时间复杂度： O(n)，平均情况下，最坏情况下为 O(n^2)。

空间复杂度： O(1)，递归栈空间。

4. 计数排序法（适用于特定情况）

如果数组中的元素范围有限，可以使用计数排序。

代码实现（Python）：

def findKthLargest(nums, k): min_val, max_val = min(nums), max(nums) count = [0] * (max_val - min_val + 1) for num in nums: count[num - min_val] += 1 for i in range(len(count) - 1, -1, -1): k -= count[i] if k <= 0: return i + min_val

时间复杂度： O(n + m)，其中 n 是数组的长度，m 是元素的范围。

空间复杂度： O(m)，用于存储计数数组。

总结：

• 排序法简单直接，但时间复杂度较高。
• 堆排序法适用于大数据集，时间复杂度较好。
• 快速选择法在平均情况下效率最高，但最坏情况下时间复杂度较差。
• 计数排序法适用于元素范围有限的情况。

根据具体需求和数据特点选择合适的解法。