You need to enable JavaScript to run this app. C++按指定行坐标垂直翻转Segment区域的报错排查与算法优化
优惠活动
大模型
产品
解决方案
定价
更多

C++按指定行坐标垂直翻转Segment区域的报错排查与算法优化

编译警告问题修复

警告成因

std::vector::size()的返回值是平台长度对应的无符号整数类型size_t,而代码中循环变量i是显式声明的有符号int类型。C++不建议直接对有符号、无符号整数做大小比较,避免出现有符号值为负时无符号值自动转换引发的逻辑错误,因此触发该警告。

修复方法

将循环变量类型调整为与size()返回值匹配的类型即可,无需修改比较逻辑:

  • 常规写法:将int i = 0;改为size_t i = 0;
  • 高兼容写法:用decltype(vec)::size_type i = 0;,这种写法不会因为后续替换容器类型再次出现类型不匹配问题。
算法效率优化方案

现有实现的性能短板

  • 遍历阶段对more、less容器调用insert(begin, *it)做头部插入:对于vector来说,头部插入需要将所有已存储元素向后移动,单步操作是O(k)复杂度(k为当前容器内元素数),全流程总插入复杂度为O(n²),数据量大时性能损耗极高
  • 拆分后对两个容器分别执行两次sort操作,属于冗余流程,垂直翻转的排序逻辑完全可以合并完成,不需要拆分多步处理

优化核心逻辑

垂直翻转的本质是行坐标映射:任意原始行号r,以flipRow为轴翻转后的行权重为2*flipRow - r,权重越小代表翻转后位置越靠上。基于这个规则,可以直接用单次排序完成所有顺序要求,完全不需要拆分容器、头部插入的冗余操作:

  1. 排序第一优先级:按翻转后的行权重从小到大排序,保证输出序列是从上到下的行顺序
  2. 排序第二优先级:同一行的Segment按colStart从小到大排序,满足同一行从左到右的输出要求
  3. 排序完成后仅需一次遍历,即可完成相对行号的归一化赋值,和原代码中counter的逻辑完全一致,不需要额外拆分处理

优化后参考代码

struct Segment
{
    int row;
    int colStart;
    int colStop;
};

std::vector<Segment> FlipVertically(const std::vector<Segment>& region, const int flipRow){
    std::vector<Segment> res = region;
    // 单次排序完成所有顺序要求
    std::sort(res.begin(), res.end(), [&flipRow](const Segment& a, const Segment& b){
        int rowA = 2 * flipRow - a.row;
        int rowB = 2 * flipRow - b.row;
        // 优先按翻转后的行位置排序
        if (rowA != rowB) {
            return rowA < rowB;
        }
        // 同一行按列从左到右排序
        return a.colStart < b.colStart;
    });
    // 归一化行号
    if (res.empty()) return res;
    int curRowIdx = 1;
    int lastFlipRow = 2 * flipRow - res[0].row;
    res[0].row = curRowIdx;
    for (size_t i = 1; i < res.size(); ++i) {
        int curFlipRow = 2 * flipRow - res[i].row;
        if (curFlipRow != lastFlipRow) {
            curRowIdx++;
            lastFlipRow = curFlipRow;
        }
        res[i].row = curRowIdx;
    }
    return res;
}

补充说明:如果输入的region本身是严格按行从上到下、同行从左到右排序的,还可以进一步优化为O(n)复杂度的实现:找到行号等于flipRow的拆分点,将拆分点以上、以下的两部分分别反转顺序后拼接,完全不需要调用sort操作。

内容的提问来源于stack exchange,提问作者Rostyslav Popov

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 16:54:04