千问 LeetCode 3027. 人员站位的方案数 II C语言实现

针对 LeetCode 3027. 人员站位的方案数 II由于点的数量 n 最大可达 1000如果采用 O(n^3) 的暴力枚举方法会超时。最优的解法是采用 排序 枚举将时间复杂度优化至 O(n^2)。核心思路1. 排序规则将所有的点按照横坐标 x 从小到大排序如果横坐标相同则按照纵坐标 y 从大到小排序。2. 枚举左上角外层循环遍历排序后的点将其作为 Alice 的位置即矩形的左上角。3. 枚举右下角内层循环向后遍历寻找 Bob 的位置即矩形的右下角。为了保证矩形内部和边缘没有其他点Bob 的纵坐标必须小于等于 Alice 的纵坐标并且 Bob 的纵坐标必须严格大于之前枚举过的所有右下角点的纵坐标维护一个当前最大纵坐标 max_y。C语言实现代码#include stdlib.h#include limits.h// 比较函数按 x 升序排序x 相同时按 y 降序排序int cmp(const void *a, const void *b) {int *p1 *(int **)a;int *p2 *(int **)b;if (p1[0] ! p2[0]) {return p1[0] - p2[0];}return p2[1] - p1[1];}int numberOfPairs(int** points, int pointsSize, int* pointsColSize) {// 1. 对点进行排序qsort(points, pointsSize, sizeof(int *), cmp);int ans 0;// 2. 枚举左上角的点 (Alice)for (int i 0; i pointsSize; i) {int y_alice points[i][1];int max_y INT_MIN; // 记录当前枚举过程中右下角点的最大纵坐标// 3. 枚举右下角的点 (Bob)for (int j i 1; j pointsSize; j) {int y_bob points[j][1];// Bob 必须在 Alice 的下方或同一水平线且纵坐标大于之前记录的最大纵坐标// 这样能保证矩形内和边界上除了 Alice 和 Bob 没有其他点if (y_bob y_alice y_bob max_y) {ans;max_y y_bob; // 更新最大纵坐标}}}return ans;}复杂度分析* 时间复杂度O(n^2)其中 n 是数组 points 的长度。排序的时间复杂度为 O(n log n)双重循环枚举点对的时间复杂度为 O(n^2)整体由 O(n^2) 主导。* 空间复杂度O(log n)主要为 qsort 排序时使用的栈空间。