题目描述：
在未排序的数组中找到第 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)，用于存储计数数组。
总结：
- 排序法简单直接，但时间复杂度较高。
- 堆排序法适用于大数据集，时间复杂度较好。
- 快速选择法在平均情况下效率最高，但最坏情况下时间复杂度较差。
- 计数排序法适用于元素范围有限的情况。
根据具体需求和数据特点选择合适的解法。