先对每行升序排序,再对每列升序排序,输出最终结果。
给定 n 行 m 列的网格。请先对每一行从左到右按升序排序,再对每一列从上到下按升序排序,输出最终结果。
例如:
1 3 2 5 行排序后 1 2 3 5 列排序后 1 2 3 5 6 2 4 4 ────→ 2 4 4 6 ────→ 1 3 4 5 5 4 1 3 1 3 4 5 2 4 4 6
行排序列排序两阶段处理排序模拟
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 n 行每行 m 个整数 |
| 输出 | n 行,每行 m 个整数 |
| 数据范围 | 1 ≤ n, m ≤ 1000 |
| 数值范围 | 整数(用 int 即可) |
| 处理顺序 | 先每行升序,再每列升序 |
sort6 5 4 3 2 1
第 1 行 6 5 → 5 6
第 2 行 4 3 → 3 4
第 3 行 2 1 → 1 2
此时网格:5 6 / 3 4 / 1 2
行排序完成
第 1 列:5、3、1 → 排序后 1、3、5
第 2 列:6、4、2 → 排序后 2、4、6
写回后网格:1 2 / 3 4 / 5 6
✅ 输出 1 2 / 3 4 / 5 6
1 2 3 4 5 6
与样例输出一致 ✓
1 3 2 5 6 2 4 4 5 4 1 3
第 1 行 1 3 2 5 → 1 2 3 5
第 2 行 6 2 4 4 → 2 4 4 6
第 3 行 5 4 1 3 → 1 3 4 5
1 2 3 5 / 2 4 4 6 / 1 3 4 5
第 1 列 1、2、1 → 1、1、2
第 2 列 2、4、3 → 2、3、4
第 3 列 3、4、4 → 3、4、4
第 4 列 5、6、5 → 5、5、6
✅ 1 2 3 5 / 1 3 4 5 / 2 4 4 6
1 2 3 5 1 3 4 5 2 4 4 6
对每列复制到临时数组,排序后整体写回
for (j = 0; j < m; j++) { vector<int> col; for (i = 0; i < n; i++) col.push_back(a[i][j]); sort(col.begin(), col.end()); for (i = 0; i < n; i++) a[i][j] = col[i]; }。在列内用相邻交换完成排序
sort 是 O(nm log n),快得多。| 方案 | 复杂度(1000×1000) | 是否可行 |
|---|---|---|
| 整列 sort | 约 2 × 10⁷ | ✅ 可行 |
| 原地冒泡 | 约 10⁹ | ❌ 可能超时 |
第一行输入 n 和 m,随后 n 行每行 m 个数。程序会先排行、再排列。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[1005][1005]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &a[i][j]); // 第一步:每一行升序排序 for (int i = 0; i < n; i++) { sort(a[i], a[i] + m); } // 第二步:每一列升序排序 for (int j = 0; j < m; j++) { vector<int> col; for (int i = 0; i < n; i++) col.push_back(a[i][j]); // 取出整列 sort(col.begin(), col.end()); // 排序 for (int i = 0; i < n; i++) a[i][j] = col[i]; // 写回整列 } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (j) printf(" "); printf("%d", a[i][j]); } printf("\n"); } return 0; }
sort(a[i], a[i] + m) 就能排一行?因为二维数组 a[i] 本质上是"第 i 行的首地址",a[i] + m 是行末的下一个位置,正好构成一个长度为 m 的一维区间。这种写法比手写内层循环更简洁。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
sort(a[i], a[i] + m) | 行排序 | 二维数组的一行就是一维区间 |
col.push_back(a[i][j]) | 取出整列 | 先把整列复制出来,避免边排边覆盖 |
sort(col.begin(), col.end()) | 列排序 | 对临时数组排序 |
a[i][j] = col[i] | 写回整列 | 排序完成后整体写回 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 2 | 1 2 / 3 4 / 5 6 | 题面样例 |
3 4 | 1 2 3 5 / 1 3 4 5 / 2 4 4 6 | 题面中的演示例子 |
1 1 | 7 | 单格 |
1 3 | 1 2 3 | 单行时只有行排序发生作用 |
3 1 | 1 / 2 / 3 | 单列时行排序不改变任何值,列排序完成升序 |
二维数组本身占 n × m,列排序时额外需要一个长度为 n 的临时数组。
✅ 约 2000 万次操作,C++ 瞬间完成。如果列排序用 O(n²),会到 10⁹ 量级,就有超时风险了。
// 二维数组的一行作为一维区间排序 for (int i = 0; i < n; i++) sort(a[i], a[i] + m); // 对每一列排序(先取出,再写回) for (int j = 0; j < m; j++) { vector<int> col(n); for (int i = 0; i < n; i++) col[i] = a[i][j]; sort(col.begin(), col.end()); for (int i = 0; i < n; i++) a[i][j] = col[i]; } // 用 vector<vector<int>> 的等价写法 vector<vector<int>> g(n, vector<int>(m)); for (auto &row : g) sort(row.begin(), row.end()); for (int j = 0; j < m; j++) { vector<int> col; for (int i = 0; i < n; i++) col.push_back(g[i][j]); sort(col.begin(), col.end()); for (int i = 0; i < n; i++) g[i][j] = col[i]; }
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 行/列排序 | 二维数组的行是一维区间 | 矩阵处理、表格排序 |
| 先取出再写回 | 避免覆盖未处理数据 | 所有原地变换类操作 |
| 复杂度估算 | 排序 O(k log k) | 选择算法时先估算运算量 |