当前位置: 首页 > news >正文

合并区间(二维vector使用,多维vector使用默认sort)

注意点:

1.sort自带的比较函数是支持多维数组比较的,使用的是字典序比较;

2.对于多维的vector,可以使用back,front,at等函数

比较例子:


二维 vector 示例

vector<vector<int>> v = { {2,5}, {1,3}, {1,2} }; sort(v.begin(), v.end());

比较过程(字典序)

  1. 比较[2,5][1,3]

    • 第一元素 2 > 1 →[1,3] < [2,5]

  2. 比较[2,5][1,2]

    • 第一元素 2 > 1 →[1,2] < [2,5]

  3. 比较[1,3][1,2]

    • 第一元素相等 1 == 1 → 比第二元素 3 > 2 →[1,2] < [1,3]

排序结果:

{ {1,2}, {1,3}, {2,5} }

左端点升序排列,相同左端点按右端点升序,正好符合区间合并需求。


三维 vector 示例

vector<vector<vector<int>>> arr = { {{1,2},{3,4}}, {{1,2},{3,3}}, {{0,9}}, {{1,1},{2,2}} }; sort(arr.begin(), arr.end());

比较过程(逐层字典序)

  1. 比较{{1,2},{3,4}}{{1,2},{3,3}}

    • 第一行[1,2] == [1,2]→ 比第二行[3,4] > [3,3]→ 后者更小

  2. 比较{{0,9}}与其它

    • 第一行[0,9]小于[1,2]→ 排最前

  3. 比较{{1,1},{2,2}}{{1,2},{3,3}}

    • 第一行[1,1] < [1,2]→ 排在前

排序结果:

{ {{0,9}}, {{1,1},{2,2}}, {{1,2},{3,3}}, {{1,2},{3,4}} }

外层二维数组按字典序排列,内层数组也按字典序排列。


总结规律

  • 二维 vector:先比每行第一个元素,不同立即决定顺序;相同则比第二个元素

  • 三维 vector:先比第一层的第一行第一个元素 → 若相等比第一行第二个元素 → 若仍相等比下一行,依此类推

  • 任意维度:逐层逐元素比较 → 遇到不同立即返回 → 相同继续比较下一位

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(),intervals.end()); vector<vector<int>> tmp; for(int i =0;i<intervals.size();i++){ int L=intervals[i][0]; int R=intervals[i][1]; if(!tmp.size() || L>tmp.back()[1]) tmp.push_back({L,R}); else tmp.back()[1]=tmp.back()[1]>R?tmp.back()[1]:R; } return tmp; } };
http://www.cnnetsun.cn/news/114296.html

相关文章:

  • ubuntu通过公网Ubuntu服务器远程桌面连接私网IPUbuntu
  • Unity学习笔记(十九)GUI控件(三)
  • IPA 深度混淆是什么意思?分析其与普通混淆的区别
  • 33、Linux 内存管理全解析
  • 5.回溯算法
  • 嵌入式模组温控策略
  • 【昇腾CANN训练营·架构篇】打破内存墙:Ascend C 算子融合(Operator Fusion)的极致心法
  • 【昇腾CANN训练营·算法篇】寻找消失的除法器:Newton Iteration 与高精度数学计算的艺术
  • 19、Linux 帧缓冲接口设计与图形库应用
  • 人才发展ℓℓ 人才盘点怎么做?这篇完全应用手册给出答案
  • 真相来了|字节跳动的人才真相:真正拉开差距的,是“人才密度”(附人才密度清单)
  • 力扣(LeetCode) 66: 加一 - 解法思路
  • HC32L130精准延时实现指南
  • 收藏必看!大学生网络安全学习5大方向,校招不踩坑,小白也能逆袭!
  • 收藏!从“黑客梦“到网络安全专家:过来人告诉你自学路线图
  • Bagisto 产品更新后,前台默认语言的内容不更信,其他语言正常。
  • 【收藏】运维转网安的黄金路径:4个高适配岗位+3步落地指南,薪资提升50%
  • 大语言模型全解析:一篇文章带你深入理解AI的强大能力!
  • 【网络】网络通信模型
  • Slimjet浏览器:基于Chromium的高效网页浏览解决方案,内置广告拦截与多功能工具
  • AMP页面还要做吗?2025替代方案及优化指南
  • 为什么你的RAG总是“一本正经地胡说八道”?EAG-RAG揭示真相,准确率暴涨300%的秘密!
  • iOS 项目中证书管理常见的协作问题
  • 理解线程不安全:从观察到原因分析
  • 《Java Web开发入门很简单》——学习笔记,新手入门,收藏这篇就够了
  • 2025年,国内外最火的10款降AI率工具亲测!(持续更新)
  • 基于大数据的餐饮食材管理系统的设计与实现开题报告
  • 基于大数据的交通信号智能控制系统的设计与实现开题报告
  • 基于大数据的交通信号智能控制系统的设计与实现任务书
  • 蜘蛛池站点优化思路分享