题目描述给定一个整数数组nums和整数k请你返回数组中第k个最大的元素。注意你需要找的是数组排序后的第 k 个最大元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。示例示例 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 nums.length 10^5-10^4 nums[i] 10^4解题思路方法一快速选择QuickSelect快速选择是快排的一种变体只需要递归处理一边数组就可以找到第 k 大元素。核心思路转化为第 n-k 小元素第 k 大元素 第(numsSize - k)小元素升序序号。partition 函数随机选 pivot交换到末尾遍历数组小于 pivot 的放左边大于 pivot 的放右边返回 pivot 最终位置递归查找如果 pivot 位置 k_smallest返回否则递归左/右子数组C 语言实现#include stdlib.h // 交换函数 void swap(int* a, int* b) { int t *a; *a *b; *b t; } // partition返回 pivot 最终位置 int partition(int* nums, int left, int right) { int pivotIndex left rand() % (right - left 1); swap(nums[pivotIndex], nums[right]); int pivot nums[right]; int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; } } swap(nums[i], nums[right]); return i; } int quickSelect(int* nums, int left, int right, int k_smallest) { if (left right) return nums[left]; int pivotIndex partition(nums, left, right); if (pivotIndex k_smallest) return nums[pivotIndex]; else if (pivotIndex k_smallest) return quickSelect(nums, left, pivotIndex - 1, k_smallest); else return quickSelect(nums, pivotIndex 1, right, k_smallest); } int findKthLargest(int* nums, int numsSize, int k) { return quickSelect(nums, 0, numsSize - 1, numsSize - k); }复杂度分析时间复杂度平均 O(n)空间复杂度O(1)原地修改数组优点最优解法适合面试缺点最坏情况 O(n²)需随机化 pivot方法二最小堆优先队列思想如果 k 比较小可以用大小为 k 的最小堆保持堆顶始终是第 k 大元素。核心思路建立大小为 k 的最小堆遍历数组元素堆没满直接放入堆满如果元素大于堆顶替换并下沉最终堆顶即为第 k 大元素C 语言实现#include stdlib.h void swap(int* a, int* b) { int t *a; *a *b; *b t; } void heapifyUp(int* heap, int index) { while (index 0) { int parent (index - 1) / 2; if (heap[parent] heap[index]) break; swap(heap[parent], heap[index]); index parent; } } void heapifyDown(int* heap, int size, int index) { while (1) { int smallest index; int left 2*index 1; int right 2*index 2; if (left size heap[left] heap[smallest]) smallest left; if (right size heap[right] size heap[right] heap[smallest]) smallest right; if (smallest index) break; swap(heap[index], heap[smallest]); index smallest; } } int findKthLargest(int* nums, int numsSize, int k) { int* heap (int*)malloc(sizeof(int) * k); int heapSize 0; for (int i 0; i numsSize; i) { if (heapSize k) { heap[heapSize] nums[i]; heapifyUp(heap, heapSize); heapSize; } else if (nums[i] heap[0]) { heap[0] nums[i]; heapifyDown(heap, heapSize, 0); } } int result heap[0]; free(heap); return result; }复杂度分析时间复杂度O(n log k)空间复杂度O(k)适用场景流式数据k 很小不允许修改原数组总结方法时间空间备注快速选择平均 O(n)O(1)面试最优解最小堆O(n log k)O(k)流式或 k 小面试小贴士第 k 大 第 n-k 小随机化 pivot 避免最坏情况堆解法更稳、适合流式数据