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,权重越小代表翻转后位置越靠上。基于这个规则,可以直接用单次排序完成所有顺序要求,完全不需要拆分容器、头部插入的冗余操作:
- 排序第一优先级:按翻转后的行权重从小到大排序,保证输出序列是从上到下的行顺序
- 排序第二优先级:同一行的Segment按
colStart从小到大排序,满足同一行从左到右的输出要求 - 排序完成后仅需一次遍历,即可完成相对行号的归一化赋值,和原代码中
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
相关产品推荐
相关产品推荐

