当前位置：首页 > news >正文

215. 数组中的第 K 个最大元素（C 语言解法 + 面试思路解析）

news 2026/5/12 21:34:57

题目描述

给定一个整数数组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; }