GESP 题解库 / 4 级题解 / [GESP202609 四级] 有序网格 · 第 25 / 25 题
GESP202609 四级 · B4580 · 中等

有序网格

先对每行升序排序,再对每列升序排序,输出最终结果。

📊
n, m ≤ 1000
网格规模
🔢
int
数值类型
⚡
O(nm log m + nm log n)
时间复杂度
🎯
两次排序
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 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
💡
人话翻译:分两步,先横后竖。第一步对每行内部排序;第二步把每一列的 m 个数收集起来排序,再写回该列。注意顺序不能颠倒,也不能"边排边修"——必须严格按题面的两步走。

🔍 关键词提取

行排序列排序两阶段处理排序模拟

已知条件

项目说明
输入第一行 n、m;随后 n 行每行 m 个整数
输出n 行,每行 m 个整数
数据范围1 ≤ n, m ≤ 1000
数值范围整数(用 int 即可)
处理顺序先每行升序,再每列升序

需要解决的问题

02
思维导图
整理解题思路的全貌
📊 先横后竖两次排序
📥 读入
n、m ≤ 1000
每行 m 个整数
用二维数组存
int 足够
➡️ 第一步:行排序
对每一行 sort
行内从左到右升序
n 次排序
每次 O(m log m)
⬇️ 第二步:列排序
对每一列:取出到临时数组
对临时数组 sort
再写回该列
m 次排序,每次 O(n log n)
⚠️ 易错点
边排边写导致数据被覆盖
顺序颠倒(先列后行)
只排了一半
临时数组未清空
03
样例手算推导
样例与题面例子的逐步演示

🧮 样例:3 × 2 网格

6 5
4 3
2 1
1
第 1 步:对每行排序

第 1 行 6 5 → 5 6

第 2 行 4 3 → 3 4

第 3 行 2 1 → 1 2

此时网格:5 6 / 3 4 / 1 2

行排序完成

2
第 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

与样例输出一致 ✓

🧮 题面 3 × 4 例子的完整演示

1 3 2 5
6 2 4 4
5 4 1 3
1
第 1 步:三行分别排序

第 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

2
第 2 步:四列分别排序

第 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
🔑
注意列排序不是"列内相邻交换",而是整列重新排序。例如第 1 列原本是 1、2、1,排序后变成 1、1、2——这说明元素可以在列内"跨越移动"。实现时最稳妥的做法是:把整列复制到临时数组 → 排序 → 整列写回。
04
解法对比
整列取出排序 vs 原地交换

⚔️ 解法对比

🟢 整列取出再写回(推荐) 推荐

对每列复制到临时数组,排序后整体写回

  • 时间 O(nm log m + nm log n)
  • 逻辑清晰
  • 不会覆盖未处理的数据
  • 代码 20 行
💡
实现: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]; }。

🟠 原地冒泡/选择排序

在列内用相邻交换完成排序

  • 时间 O(n²m),n = 1000 时约 10⁹
  • 可能超时
  • 代码更啰嗦
  • 且容易写错
⚠️
为什么不用:本题 n, m ≤ 1000,O(n²m) 最坏约 10⁹ 次交换,很可能超时。直接用标准 sort 是 O(nm log n),快得多。

📈 性能对比

方案复杂度(1000×1000)是否可行
整列 sort约 2 × 10⁷✅ 可行
原地冒泡约 10⁹❌ 可能超时
05
算法流程图
先排每行,再排每列
开始读入 n、m 和网格 a[][]第一步:i 从 0 到 n−1,对第 i 行升序排序第二步:j 从 0 到 m−1把第 j 列的所有元素复制到临时数组 col对 col 升序排序,再写回第 j 列所有列都处理完了吗?输出网格结束j 加 1 继续下一列
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📊 有序网格处理器

第一行输入 n 和 m,随后 n 行每行 m 个数。程序会先排行、再排列。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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]写回整列排序完成后整体写回
⚠️
三个坑:① 边排边写(比如找到最小值就直接写到 a[0][j]),会把还没比较的元素覆盖掉——必须先把整列取出来;② 顺序颠倒(先列后行),结果会完全不同;③ 用冒泡排序处理列,n = 1000 时可能超时。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 2
6 5 / 4 3 / 2 1
1 2 / 3 4 / 5 6题面样例
3 4
1 3 2 5 / 6 2 4 4 / 5 4 1 3
1 2 3 5 / 1 3 4 5 / 2 4 4 6题面中的演示例子
1 1
7
7单格
1 3
3 1 2
1 2 3单行时只有行排序发生作用
3 1
3 / 1 / 2
1 / 2 / 3单列时行排序不改变任何值,列排序完成升序
✅
自查清单:① 先排行再排列了吗?② 列是整列取出排序的吗?③ 输出格式对吗?

🚨 易错点清单

⚠️
边排边写:必须先把整列取出到临时数组,排序后再整体写回,否则会覆盖未处理的数据。
⚠️
顺序颠倒:必须"先全部行排序、再全部列排序",不能交替进行。
⚠️
用冒泡排序处理列:n = 1000 时 O(n²m) 约 10⁹,可能超时,应使用标准 sort。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(nm log m + nm log n)
空间复杂度
O(nm)
n, m 最大
1000
运算量
约 2 × 10⁷

时间怎么算的?

空间都用在哪?

二维数组本身占 n × m,列排序时额外需要一个长度为 n 的临时数组。

✅ 约 2000 万次操作,C++ 瞬间完成。如果列排序用 O(n²),会到 10⁹ 量级,就有超时风险了。

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)选择算法时先估算运算量
🌟
思考题:如果题目改成"先列排序、再行排序",结果会和现在一样吗?(提示:一般不一样。可以自己用样例数据试试:先列后行得到的结果通常与先行后列不同。这说明"排序顺序"是不可交换的——所以读题时务必确认清楚处理顺序。)