企业官网建设流程全解析

最近在刷LeetCode的时候，连续几道题都遇到了“Top K”类的问题，从数据流中的第K大元素到前K个高频单词，套路都差不多，但用C语言实现起来，每个题都还有各自的坑。今天想单独聊聊第973题“K Closest Points to Origin”，中文就是“最接近原点的K个点”。这道题在LeetCode上标注为Medium，但我觉得它的价值被严重低估了——它表面上考的是排序，实际上把“排序、堆、快速选择”三种思路串在了一道题里，而且因为输入是二维坐标数组，还额外牵扯到结构体排序、比较函数怎么写、内存怎么分配这些C语言特有的问题。无论你是刚刷完C语言基础语法准备进阶，还是在准备面试前想集中突破算法题，这道题都值得仔细啃一遍。

先说下题目本身：给定一个数组points，里面每个元素是一个二维坐标点(x, y)，另外给一个整数K，要求返回距离原点(0,0)最近的K个点。注意，这里说的距离是欧几里得距离，也就是sqrt(x*x + y*y)，但因为开根号是单调函数，比较距离大小时直接用x*x + y*y就好，完全没必要真的去调sqrt()，既省时间又省去浮点数精度问题的麻烦。

这道题从暴力到最优大概有四五种写法，但核心思路就三类：全排序、维护大小为K的堆、快速选择。我打算把三种主流方案都拆开讲一遍，重点放在C语言实现上，包括qsort回调函数的陷阱、手写堆的细节、快速选择的partition边界处理，最后再整理一些我实际提交时踩过的坑。这篇文章适合已经掌握C语言基本语法、想进阶算法题的读者，也适合正在准备技术面试、需要把这道题吃透的朋友。

1. 题目理解与思路拆解

1.1 题面解析与核心数学点

先再把题意掰开揉碎一下。LeetCode 973的输入是两个参数：points是一个二维整数数组，pointsSize表示点的个数，pointsColSize记录每个一维数组的长度（这道题固定是2）；k是你要返回的最近点的数量。返回值是一个二维数组，要求按任意顺序返回距离原点最近的k个点即可，这也算是降低了一点难度——如果要求按距离排序返回，那又是另一回事了。

核心的数学点在于距离的计算。原点到点(x, y)的欧几里得距离公式是d = sqrt(x*x + y*y)。大家通常不会在这里卡住，但有个细节值得强调：平面上的比较可以用距离平方来替代，因为sqrt在定义域内是单调递增的。如果你a < b，那么sqrt(a) < sqrt(b)一定成立，所以比较x1*x1 + y1*y1和x2*x2 + y2*y2就能确定两个点谁离原点更近。这个替代带来两个直接好处：一是避免调用sqrt()的开销，二是不用考虑浮点数相等比较的麻烦——在算法题里能用整数运算就尽量不要引入浮点，这是C语言刷题的基本修养。

另一个容易被忽略的数学点是坐标范围。题目给的坐标范围是[-10^4, 10^4]，平方后每个分量最大是10^8，相加后距离平方最大是2 * 10^8，这个数值在int范围内（INT_MAX约2.1 * 10^9），所以用int存储距离平方是安全的。但如果你把代码扩展到三维坐标、或者坐标范围扩大，就一定要小心溢出，那时候得换long long。这也是LeetCode C语言题解里一个比较常见的坑：距离平方的计算结果超出int范围导致答案错误，排查半天发现是溢出问题。

1.2 为什么这题适合用C语言深挖

说实话，如果这题用C++或Python写，代码可以非常短。C++直接nth_element或者priority_queue走起，Python直接sorted(points, key=lambda p: p[0]*p[0]+p[1]*p[1])[:k]，一行搞定。但用C语言就不一样了——C语言的标准库没有内置的堆结构，也没有方便的比较器机制，所有事情都得自己搭。

这恰恰是这道题对C语言选手的价值所在。我见过太多人刷题只追求“AC”，用Python调库调习惯了，碰到C语言手写堆就懵。而面试场景里，有些面试官还就喜欢让你用C语言手写堆或者快速选择，考察你“是不是真的理解数据结构而不只是会用库”。973这道题正好覆盖了高频面试的三个考点：排序（qsort的灵活使用）、堆（Top K的标准解法）、快速选择（平均O(N)的进阶算法），一道题等于三道题。

我的建议是：这道题至少刷两遍。第一遍用最直觉的排序法AC，理解题目的基本模型；第二遍再用堆和快速选择分别实现，重点体会“不排序全部元素”的思路。第二遍的收获远比第一遍大，因为你会真正理解“Top K问题”的精髓：K远小于N时，全排序是一种巨大的浪费。

1.3 三种解法选型：从暴力到最优

先给出一个宏观的对比，后面两节再分别展开细节。

什么时候选哪种？我的经验是：排序法最适合作为第一遍刷题的标准答案，逻辑简单、不易写错；堆解法适合在K远小于N的场景使用，比如N是百万级、K是几十，这时候N log K的优势十分明显；而快速选择是最接近“最优解”的方案，平均线性复杂度，但需要扎实的partition功底，而且要理解最坏情况的成因——数据分布不均匀时可能退化到O(N^2)，不过实际工程和面试中，快速选择的平均表现非常优秀，是这题最好的进阶答案。

2. 排序法：最直接的AC路径

2.1 为什么先写排序法

排序法是理解成本最低的方案：算出每个点到原点的距离平方，按距离对全部点排序，然后取前K个返回。这几乎是所有人的第一反应，而且C语言标准库提供了qsort这个通用排序函数，用起来并不复杂。

但qsort有个众所周知的痛点——它的比较函数（comparator）需要你自己写，而且返回值有严格约定：第一个参数小于第二个参数时返回负数，相等返回0，大于返回正数。很多人第一次用qsort时都会在比较函数上翻车，常见错误是直接用return a - b;，这在整数排序里通常情况下可行，但在距离平方的比较上可能出现问题——距离平方的范围在0 ~ 2*10^8之间，两个数相减的结果完全落在int范围内，所以return a.dist - b.dist;在这道题里其实不会溢出。但为了养成好习惯，我还是建议写成return (a.dist > b.dist) - (a.dist < b.dist);这种写法，能适配更大范围的数据，也不会因为减法溢出导致错误。

2.2 结构体设计与qsort回调函数

因为要同时对“点的坐标”和“该点到原点的距离平方”两个信息排序，最简单的做法是定义一个结构体：

typedef struct { int x; int y; int dist; } Point;

然后遍历原始数组，把每个点坐标和距离平方填充到结构体数组里。排序时按dist字段排序：

int cmp(const void *a, const void *b) { const Point *pa = (const Point *)a; const Point *pb = (const Point *)b; return (pa->dist > pb->dist) - (pa->dist < pb->dist); }

这里为什么要用结构体而不是单独记录距离？因为排序之后你还得把坐标原样返回，如果用“距离索引对”之类的结构，后续取坐标时还要映射回原数组，徒增复杂度。结构体一次到位，代码也更清晰。qsort回调函数的两个参数是const void *，C语言里必须显式转换成具体的结构体指针，这一步不能省，也不能直接解引用void *，这是很多初学者编译报错的原因。

2.3 完整代码与复杂度分析

完整的排序法实现如下：

/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ typedef struct { int x; int y; int dist; } Point; int cmp(const void *a, const void *b) { const Point *pa = (const Point *)a; const Point *pb = (const Point *)b; return (pa->dist > pb->dist) - (pa->dist < pb->dist); } int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) { if (pointsSize == 0 || k == 0) { *returnSize = 0; *returnColumnSizes = NULL; return NULL; } Point *arr = (Point *)malloc(sizeof(Point) * pointsSize); for (int i = 0; i < pointsSize; i++) { arr[i].x = points[i][0]; arr[i].y = points[i][1]; arr[i].dist = points[i][0] * points[i][0] + points[i][1] * points[i][1]; } qsort(arr, pointsSize, sizeof(Point), cmp); int **res = (int **)malloc(sizeof(int *) * k); *returnColumnSizes = (int *)malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { res[i] = (int *)malloc(sizeof(int) * 2); res[i][0] = arr[i].x; res[i][1] = arr[i].y; (*returnColumnSizes)[i] = 2; } *returnSize = k; free(arr); return res; }

这段代码在LeetCode上可以直接AC。时间和空间复杂度都是O(N log N)和O(N)。pointsSize是N。排序数组占了O(N)的额外内存，而结果数组本身是题目要求返回的，不计入额外空间的话也可以说额外空间是O(N)。

排序法的好处不仅是好写，还在于它是一个绝佳的“对照基准”。后续你写堆或快速选择时，跑同样的测试用例和排序法对比输出，能快速定位是哪一步写错了。

3. 堆解法：当K远小于N时的利器

3.1 最大堆的思路：为什么不是最小堆

排序法把N个点全排了，但题目只要K个最近的，如果K远小于N，这显然浪费。堆解法就是针对这个场景优化的：维护一个容量为K的容器，遍历所有点，不断更新这个容器，让它始终保存“当前已遍历点中距离最近的K个点”。遍历结束后，容器里的K个点就是答案。

关键在于：这个容器用什么数据结构？答案是最大堆，而不是最小堆。

很多人直觉上会选最小堆——既然是找“最近的K个”，堆顶放最小的不行吗？我们推演一下就知道问题在哪。如果维护一个大小为K的最小堆，堆顶是堆内距离最小的点。遍历到一个新点时，只要新点距离比堆顶大，说明它比当前的“最近K个”中最小的还远，可以丢弃；反过来，如果新点距离比堆顶小，它应该进入堆，但接下来堆内会多出K+1个点，你要把谁移出去？此时堆顶是K+1个点中“最近的”那个，把堆顶丢出去的话，等于把“K+1个点里最近的那个”干掉了，这显然不对——我们是要保留K个最近的，不是丢弃最近的。

换成最大堆就顺了。最大堆的堆顶是堆内K个候选点中距离最大的那个（也就是当前最远的候选点）。遍历新点时，只有新点距离比堆顶小，才值得“挤掉”当前最远的候选点——把堆顶弹出，把新点插入，堆重新调整后，堆内始终是遍历到目前最近的K个点。这一步操作的时间复杂度是O(log K)，总时间复杂度O(N log K)。当K远小于N时，这个复杂度明显优于O(N log N)。

3.2 C语言手写堆：从建堆到调整

C语言没有现成的堆，需要自己写。这里涉及三个子函数：siftDown（下沉调整）、siftUp（上浮调整）、buildHeap（建堆，也可以直接逐个插入）。也可以用siftUp实现插入，然后用siftDown实现弹出堆顶。

先定义一个“距离索引节点”的结构，因为堆里既要存距离，还要能回溯到原始坐标：

typedef struct { int dist; int idx; // 原始数组中的下标 } HeapNode;

堆用数组存储，下标从0开始，父节点下标是(i-1)/2，左右孩子是2*i+1和2*i+2，这是C语言手写堆最基础的布局，必须烂熟于心。

buildHeap的过程：从最后一个非叶节点开始，逐个执行siftDown。最后一个非叶节点的下标是n/2 - 1（整数除法），这个公式要记住，它是建堆的起点。

void siftDown(HeapNode *heap, int n, int i) { while (1) { int smallest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && heap[left].dist < heap[smallest].dist) { smallest = left; } if (right < n && heap[right].dist < heap[smallest].dist) { smallest = right; } if (smallest == i) { break; } HeapNode tmp = heap[i]; heap[i] = heap[smallest]; heap[smallest] = tmp; i = smallest; } }

建堆是O(K)的。接下来每次插入新节点时，先把它放到数组末尾，然后不断和父节点比较，如果比父节点小就交换，也就是siftUp：

void siftUp(HeapNode *heap, int i) { while (i > 0) { int parent = (i - 1) / 2; if (heap[i].dist < heap[parent].dist) { HeapNode tmp = heap[i]; heap[i] = heap[parent]; heap[parent] = tmp; i = parent; } else { break; } } }

删除堆顶时，把数组最后一个元素放到堆顶，然后对堆顶执行siftDown。这是C语言手写堆的三个基本操作，建议练到闭着眼都能写出来，因为面试中堆相关的题基本都靠这些。

3.3 堆解法的完整实现与细节

堆解法的完整流程如下：

int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) { if (k == 0) { *returnSize = 0; return NULL; } // 用前k个点建立大小为k的最大堆（直接用距离的相反数来模拟最大堆） HeapNode *heap = (HeapNode *)malloc(sizeof(HeapNode) * k); for (int i = 0; i < k; i++) { int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1]; heap[i].dist = -dist; // 取负，让最小堆逻辑变成“最大堆” heap[i].idx = i; } // 建堆（最小堆，存的是负距离，堆顶绝对值最大，等价于最大堆） for (int i = k / 2 - 1; i >= 0; i--) { siftDown(heap, k, i); } // 遍历剩余点 for (int i = k; i < pointsSize; i++) { int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1]; // 堆顶存的是 -最远距离，如果新点距离“负值”更小说明原距离更大，跳过 if (-dist > heap[0].dist) { // 等价于 dist < -heap[0].dist // 替换堆顶 heap[0].dist = -dist; heap[0].idx = i; siftDown(heap, k, 0); } } // 从堆中取出K个点 int **res = (int **)malloc(sizeof(int *) * k); *returnColumnSizes = (int *)malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { int idx = heap[i].idx; res[i] = (int *)malloc(sizeof(int) * 2); res[i][0] = points[idx][0]; res[i][1] = points[idx][1]; (*returnColumnSizes)[i] = 2; } *returnSize = k; free(heap); return res; }

这里我用了取负距离的小技巧：C语言里写最大堆要单独改比较逻辑，而取负后就能复用最小堆的代码，堆顶的负值最小，对应的原始距离最大。这个技巧在很多需要最大堆的题里都通用，值得记下来。

不过堆解法也不是没有缺点：代码量比排序法大不少，而且容易在堆的边界条件上出错。比如k == pointsSize时，走完整个流程会发现堆里就是全部点；k == 1时，堆的建堆起点k/2-1 = -1，这个循环就不会执行，要确保代码能handle这种情况。我的建议是写完后拿k=1和k=pointsSize两个边界用例跑一遍，再提交。

4. 快速选择：平均O(N)的最优方案

4.1 快速选择原理与partition

快速选择（QuickSelect）是所有解法中最精彩的一个，它把快速排序的partition思想直接用在了“找第K小”的问题上。这里我们不需要全局有序，只要能把“第K小的元素”放到它最终的位置上，并且保证它左边的元素都不大于它，那左边的K个元素就是答案。

快速选择的核心操作是partition。以数组某个元素为基准（pivot），把数组分成两部分：左边都不大于pivot，右边都大于pivot。如果partition结束后pivot的下标正好是k-1，那pivot左边（含pivot）恰好K个点就是最近的K个；如果pivot下标小于k-1，说明答案整体在右边区间，递归处理右边；反之处理左边。这个过程每次只需要递归一边，平均复杂度O(N)，因为每次partition大概把区间缩小一半，N + N/2 + N/4 + ... = 2N。

partition的写法有多种，我比较推荐的是Lomuto分区或者Hoare分区。Lomuto分区代码更短，但需要注意基准元素的选择。如果用固定基准（比如每次取区间第一个），在极端的输入下（比如点已经按距离从近到远排好了）会退化成O(N^2)——每次partition只排除一个元素，这跟快速排序退化的原因一模一样。解决方法是随机选基准或者取“三数取中”。LeetCode的测试用例不一定针对这个做特殊构造，但为了稳健，我还是建议至少用随机选基准。

4.2 C语言实现：结构体数组与交换操作

快速选择需要频繁交换元素，所以最好还是用结构体数组，方便直接交换整个节点。实现大致如下：

typedef struct { int x; int y; int dist; } Point; int partition(Point *arr, int left, int right) { // 随机选基准，避免最坏情况 int pivotIdx = left + rand() % (right - left + 1); int pivotDist = arr[pivotIdx].dist; // 把基准换到末尾，方便分区 Point tmp = arr[pivotIdx]; arr[pivotIdx] = arr[right]; arr[right] = tmp; int storeIdx = left; for (int i = left; i < right; i++) { if (arr[i].dist < pivotDist) { tmp = arr[i]; arr[i] = arr[storeIdx]; arr[storeIdx] = tmp; storeIdx++; } } // 把基准放回最终位置 tmp = arr[storeIdx]; arr[storeIdx] = arr[right]; arr[right] = tmp; return storeIdx; } void quickSelect(Point *arr, int left, int right, int k) { if (left >= right) { return; } int pivotIndex = partition(arr, left, right); if (pivotIndex == k) { return; } else if (pivotIndex < k) { quickSelect(arr, pivotIndex + 1, right, k); } else { quickSelect(arr, left, pivotIndex - 1, k); } }

注意这里的quickSelect的k是“需要确定第k个位置（0-based）”，也就是最终要保证下标0到k-1是最近的K个元素。当pivotIndex == k时，第k个元素（0-based）已经在正确位置，那么前k个元素都小于等于它，直接返回即可。

有个容易混淆的点：如果k=3，我们需要下标0、1、2三个位置最终确定下来。当pivotIndex == 3时，说明下标3的位置是第4小的元素，那么0~2自然就是最小的3个，任务完成。这也是为什么判断条件是pivotIndex == k而不是pivotIndex == k-1，这个细节很多人会被绕晕，我在写的时候专门踩过这个坑。

4.3 完整代码与工程化考量

完整的快速选择解法如下：

int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) { if (k == 0) { *returnSize = 0; *returnColumnSizes = NULL; return NULL; } Point *arr = (Point *)malloc(sizeof(Point) * pointsSize); for (int i = 0; i < pointsSize; i++) { arr[i].x = points[i][0]; arr[i].y = points[i][1]; arr[i].dist = points[i][0] * points[i][0] + points[i][1] * points[i][1]; } srand(time(NULL)); // 初始化随机种子 quickSelect(arr, 0, pointsSize - 1, k); int **res = (int **)malloc(sizeof(int *) * k); *returnColumnSizes = (int *)malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { res[i] = (int *)malloc(sizeof(int) * 2); res[i][0] = arr[i].x; res[i][1] = arr[i].y; (*returnColumnSizes)[i] = 2; } *returnSize = k; free(arr); return res; }

在工程化层面有几个细节需要注意。一是rand()和time(NULL)需要包含<stdlib.h>和<time.h>头文件，LeetCode的环境默认不会帮你包含全部头文件，所以记得自己加。二是快速选择是“破坏性”操作，它直接修改了arr中元素的顺序，但因为arr是我们自己malloc的副本，不影响原始数据，这一点没问题。三是空间复杂度可以做到O(1)额外空间（如果忽略结果数组），比排序和堆都更省内存。

快速选择的平均时间复杂度是O(N)，最坏O(N^2)。在面试中如果你写快速选择，面试官通常会追问“最坏情况是什么？如何避免？”，这时候如果能答出随机选基准或者三数取中，就是一个加分项。

5. 三种解法对比与面试场景选择

5.1 横向评测：时间、空间、代码量

三种方法我们都实现了一遍，我建议你在本地把三个版本都跑一遍，用相同的测试用例对比结果。这里我整理一个横向对比表：

从大数据量的角度看，快速选择在平均意义上有最好的时间复杂度，而且不依赖K的大小；堆的优势在于K特别小、且数据可能以流式方式到达的场景——比如实时数据流里维护Top K，堆是唯一能在线处理的方案；排序法最稳妥，且如果后续要求按距离排好序返回，排序法甚至不用改代码。

5.2 面试官视角：这题在考你什么

这道题在面试中的区分度很高，可以考察好几层能力。第一层是基础的数据结构认知：能不能想到用最大堆维护Top K，或者想到快速选择；第二层是C语言功底：比较函数的写法、堆的调整逻辑、指针和内存管理；第三层是复杂度分析能力：能不能说出三种方法的时间空间复杂度，以及各自的适用场景。

我面试别人的时候，如果候选人写排序法，我会追问“如果数据量是十亿级，K是100，排序还合适吗？”；写堆的会追问“为什么用最大堆不用最小堆，堆的建堆复杂度是多少，插入复杂度是多少”；写快速选择的会追问“最坏情况是哪种输入，怎么优化”。每一层追问都在筛掉“背答案”的候选人。所以我的建议是：不要满足于AC，把三种解法都吃透，面试时主动说出“我还可以用最大堆或快速选择优化”，这会比只甩一个qsort实现有说服力得多。

5.3 我的答题偏好与建议

我个人在实际刷题和面试中的偏好是：如果时间紧张，先写排序法保底；如果追求最优，用快速选择。堆解法我更多是在“流式数据”类题目里才优先考虑，因为纯静态数组的Top K问题，快速选择在平均意义下总是更优。

不过这里必须强调一个前提：快速选择的代码对partition的要求比较高，如果你对partition的边界条件不够熟，调试起来可能比堆还费时间。我的建议是平时练题时把快速选择作为标准答案去练，但真正面试时，如果面试官没有明确要求最优复杂度，写堆解法其实是最稳的——因为堆的时间复杂度有强保证，不像快速选择那样存在最坏情况的解释成本。这个取舍基于一个简单的原则：面试中稳定性优先于炫技，先把正确的东西讲清楚，再谈优化。

6. 常见问题与排查技巧实录

6.1 比较函数和排序相关的坑

第一个坑是qsort比较函数返回result_a - result_b的溢出问题。前面说过，这道题距离平方的范围在0 ~ 2*10^8，相减不会溢出，但这个写法其实是个定时炸弹。如果你之后遇到坐标范围更大的题，比如[-10^9, 10^9]，距离平方能到2 * 10^18，超出int范围，任何时候做减法都可能溢出。稳妥的写法永远是：

return (pa->dist > pb->dist) - (pa->dist < pb->dist);

这个写法做了两次比较，编译器会优化成条件判断，不会真的调用两次比较函数，性能损失可以忽略。

第二个坑是排序结果不稳定导致输出顺序变化。题目明确说返回顺序任意，但如果你在本地调试时希望输出稳定，可以使用带原始下标的排序——比较距离相等时再比较下标。这只是调试方便，刷题时不需要。

6.2 内存分配与返回值约定

LeetCode的C语言函数签名里有*returnColumnSizes这个参数，很多人第一次见到会懵。它的作用是把二维数组每一行的长度告诉调用方，虽然本题每行固定都是2，但仍然要为其分配k个int的空间并填充。漏掉这一步会导致运行时错误。另外，res数组中每个res[i]都要单独malloc，不能只malloc一次二维数组——除非你用int (*res)[2]这样的变长数组语法，但LeetCode通常要求返回int**，所以逐行malloc是标准做法。

还有一个常见的“内存泄露”警告问题：在刷题平台上，你的代码内malloc的内存由引擎自动回收，所以不需要手动free答案数组。但你malloc的临时数组（比如结构体数组和堆数组）一定要记得free，否则在LeetCode的内存检测下可能被判为内存泄露。

6.3 边界条件与极端用例

这道题的边界条件集中在几个位置。k == 0：不返回任何点，此时returnSize设为0，returnColumnSizes可以设为NULL，不能再malloc大小为0的数组再返回，有些编译器对malloc(0)返回的指针是否为NULL无法保证，最好直接返回NULL。pointsSize == 0：同理。k == pointsSize：直接返回所有点，三种解法都能自然处理，但排序法和快速选择要注意数组越界的问题。还有一个容易忽略的是points[i][0] * points[i][0]的中间溢出——虽然前面算过范围没问题，但我建议仍然先强转long long再乘：

long long d = (long long)points[i][0] * points[i][0] + (long long)points[i][1] * points[i][1];

然后把它存在long long字段里。代码稍微变了点，但安全系数高很多，尤其是当你想把这道题的解法复用到别的变种题时，这一步能帮你省掉排查溢出的时间。

最后分享一个我实际调试时用到的小技巧：先写排序法，然后在main函数里构造几个小用例，比如points = [[1,3],[-2,2],[2,-2]]，k=1；points = [[3,3],[5,-1],[-2,4]]，k=2；再多跑一个k == pointsSize的边界用例。排序法跑通之后，再用堆和快速选择跑同一批用例，用排序法的结果作为基准比对输出。一旦堆或快速选择的输出不一致，就能很快定位是哪个环节写错了——这个“用简单实现验证复杂实现”的思路，不只是针对这道题，刷任何算法题都适用。

7. 总结与进一步练习建议

这道题的核心收获不只是“会做973”，而是建立一套解决“Top K类问题”的完整思路框架。建议你接着刷四道题巩固：LeetCode 215（数组中的第K个最大元素）、347（前K个高频元素）、692（前K个高频单词）、295（数据流的中位数，涉及双堆技巧）。这几道题和973一起刷，你会发现它们的底层模型高度相似——要么排序、要么堆、要么快速选择，而C语言手写堆和partition的能力会在反复练习中逐渐内化。

我个人在实际刷题中的体会是：把一道Medium题用三种方法吃透，比囫囵吞枣刷十道Easy题收获大得多。973这道题恰好是一个完美样本：题目简洁但解法层次丰富，既能夯实qsort和结构体排序的基础，也能训练手写堆和partition的硬功夫。如果你现在还在纠结“为什么我刷过的题记不住”，很可能是因为每道题只写了一种解法，没有深入比较不同方案的差异。找几道像973这样“一题多解”的题目，用多种写法反复训练，你的算法敏感度会有明显的提升。