目录引言问题定义方法一排序法最直观思路方法二堆优先队列法思路复杂度分析方法三快速选择法Quick Select方法四计数排序法数据范围有限时方法对比与选择建议总结引言在算法面试和日常开发中TOP-K问题是一类非常经典的问题。今天我们来探讨其中一个变体给定一个无序数组找出其中最小的K个元素。这个问题看似简单实则蕴含着丰富的算法思想我们将从暴力解法到最优解逐一剖析并给出C实现。问题定义输入无序数组 arr整数 K (1 ≤ K ≤ arr.length) 输出数组中最小的K个元素顺序不限 示例arr [3,2,1,5,6,4], K 2 → 输出 [1,2] 或 [2,1]方法一排序法最直观思路最简单的思路将数组排序然后取前K个元素。这种方法虽然时间复杂度较高但代码简单适合K接近N或对性能要求不高的场景。复杂度分析时间复杂度O(N log N)主要来自排序空间复杂度O(1)原地排序或 O(N)使用额外空间C代码实现#include vector #include algorithm using namespace std; vectorint topKBySort(vectorint nums, int k) { if (k nums.size()) return nums; sort(nums.begin(), nums.end()); return vectorint(nums.begin(), nums.begin() k); }方法二堆优先队列法思路维护一个大小为K的最大堆1). 遍历数组元素2). 当堆的大小小于K时直接入堆3). 当堆的大小等于K时如果当前元素小于堆顶堆中最大元素则弹出堆顶将当前元素入堆遍历结束后堆中保存的就是最小的K个元素。为什么用最大堆而不是最小堆因为我们需要快速访问当前K个候选元素中的最大值以便判断新元素是否需要加入。复杂度分析时间复杂度O(N log K)每个元素都可能进行堆操作空间复杂度O(K)堆的存储空间C代码实现#include vector #include queue using namespace std; vectorint topKByHeap(vectorint nums, int k) { if (k nums.size()) return nums; if (k 0) return {}; // 使用最大堆优先队列默认是最大堆 priority_queueint maxHeap; for (int num : nums) { if (maxHeap.size() k) { maxHeap.push(num); } else if (num maxHeap.top()) { maxHeap.pop(); maxHeap.push(num); } } // 将堆中的元素取出 vectorint result; while (!maxHeap.empty()) { result.push_back(maxHeap.top()); maxHeap.pop(); } return result; }方法三快速选择法Quick Select思路基于快速排序的分区思想1). 选择一个基准元素pivot2). 将数组分区使得左边元素都小于等于pivot右边都大于pivot3). 如果pivot的位置恰好是K-1则左边0到K-1就是前K小元素4). 如果pivot的位置大于K-1则在左边继续查找5). 如果pivot的位置小于K-1则在右边继续查找这种方法能在平均情况下达到线性时间复杂度。复杂度分析时间复杂度平均O(N)最坏O(N²)可通过随机化pivot优化空间复杂度O(1)原地操作不考虑递归栈C代码实现#include vector #include cstdlib #include ctime using namespace std; class QuickSelect { private: int partition(vectorint nums, int left, int right) { // 随机选择pivot避免最坏情况 int randomIndex left rand() % (right - left 1); swap(nums[randomIndex], nums[right]); int pivot nums[right]; int i left; // i指向小于等于pivot的区域边界 for (int j left; j right; j) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; } } swap(nums[i], nums[right]); return i; // 返回pivot的最终位置 } void quickSelect(vectorint nums, int left, int right, int k) { if (left right) return; int pivotIndex partition(nums, left, right); if (pivotIndex k) { return; } else if (pivotIndex k) { quickSelect(nums, left, pivotIndex - 1, k); } else { quickSelect(nums, pivotIndex 1, right, k); } } public: vectorint topKByQuickSelect(vectorint nums, int k) { if (k nums.size()) return nums; if (k 0) return {}; srand(time(nullptr)); quickSelect(nums, 0, nums.size() - 1, k - 1); // 前k个元素就是最小的k个但未排序 return vectorint(nums.begin(), nums.begin() k); } };方法四计数排序法数据范围有限时思路当数组元素的范围较小且已知时可以使用计数排序的思想1). 统计每个元素出现的频率2). 从小到大遍历可能的元素值累加计数直到达到K个这种方法在某些特定场景下效率极高。复杂度分析时间复杂度O(N range)range为元素取值范围大小空间复杂度O(range)C代码实现#include vector #include algorithm using namespace std; vectorint topKByCounting(vectorint nums, int k) { if (k nums.size()) return nums; if (k 0) return {}; // 假设元素范围在[0, 10000]之间 int maxVal *max_element(nums.begin(), nums.end()); int minVal *min_element(nums.begin(), nums.end()); vectorint count(maxVal - minVal 1, 0); // 统计频率 for (int num : nums) { count[num - minVal]; } // 收集结果 vectorint result; for (int i 0; i count.size(); i) { while (count[i] 0 result.size() k) { result.push_back(i minVal); count[i]--; } if (result.size() k) break; } return result; }方法对比与选择建议方法时间复杂度空间复杂度适用场景排序法O(N log N)O(1)K接近N代码简单优先堆方法O(N log K)O(K)N很大K较小快速选择平均O(N)O(1)N很大需要高效且不要求有序计数排序O(Nrange)O(range)数据范围小元素分布集中总结TOP-K问题虽然基础但涵盖了排序、堆、分治等多种算法思想。在实际应用中我们应该根据数据规模和特点选择合适的方法如果K接近N排序法简单直接如果数据量巨大且K较小堆方法是工业界最常用的方案如果追求极致性能且能接受最坏情况快速选择是不错的选择如果数据范围有限计数排序可能带来惊喜理解这些方法不仅能解决TOP-K问题更能帮助我们建立算法思维应对更复杂的场景。