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

【C++习题】20. 两个数组的交集

题目:349. 两个数组的交集 - 力扣(LeetCode)

链接🔗:349. 两个数组的交集 - 力扣(LeetCode)

题目:

1532654fe5b5c5f74d892dad1a960298


代码:

class Solution {
public:// 函数功能:求两个数组的交集// 参数:两个整型vector数组的引用// 返回值:包含交集元素的vectorvector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 构造两个set,利用set自动去重和排序的特性// 用nums1和nums2的迭代器区间初始化setset<int> s1(nums1.begin(), nums1.end());  // nums1中的不重复元素set<int> s2(nums2.begin(), nums2.end());  // nums2中的不重复元素// 创建结果数组,用于存储交集元素vector<int> ret;// 获取两个set的起始迭代器auto it1 = s1.begin();auto it2 = s2.begin();// 同时遍历两个set,直到其中一个遍历完while(it1 != s1.end() && it2 != s2.end()){if(*it1 < *it2)  {// 如果s1当前元素小,移动s1的迭代器it1++;}else if(*it1 > *it2){// 如果s2当前元素小,移动s2的迭代器it2++;}else  // *it1 == *it2{// 相等说明是交集元素ret.push_back(*it1);  // 将交集元素加入结果数组// 两个迭代器都要往后移动it1++;it2++;}}return ret;  // 返回结果数组}
};

算法思路解析:

  1. 预处理:
    • 将两个数组转换为set,实现去重和排序
    • 时间复杂度:O(NlogN),空间复杂度:O(N)
  2. 求交集:
    • 利用set有序的特性,用双指针(迭代器)同时遍历两个set
    • 类似归并排序的思路,比较两个当前元素:
      • 如果s1当前元素小,移动s1迭代器
      • 如果s2当前元素小,移动s2迭代器
      • 如果相等,就是交集元素,加入结果数组,两个迭代器都移动
    • 时间复杂度:O(min(N,M))NM是两个set的大小
  3. 优势:
    • 利用set的特性自动去重和排序
    • 双指针遍历的方式效率高
    • 代码简洁易懂
http://www.lryc.cn/news/518088.html

相关文章:

  • 小R的蛋糕分享
  • 基于Arduino的FPV头部追踪相机系统
  • 使用 PyTorch 自定义数据集并划分训练、验证与测试集
  • VSCode 插件
  • Windows使用AutoHotKey解决鼠标键连击现象(解决鼠标连击、单击变双击的故障)
  • Linux 环境(Ubuntu)部署 Hadoop 环境
  • 如何在Windows 11 WSL2 Ubuntu 环境下安装和配置perf性能分析工具?
  • Docker运维高级容器技术知识点总结
  • react-quill 富文本组件编写和应用
  • LabVIEW轴承性能测试系统
  • 【《游戏编程模式》实战04】状态模式实现敌人AI
  • 借助免费GIS工具箱轻松实现las点云格式到3dtiles格式的转换
  • 科研绘图系列:R语言科研绘图之标记热图(heatmap)
  • 【轻松学C:编程小白的大冒险】--- C语言简介 02
  • 《HeadFirst设计模式》笔记(上)
  • 数据结构:ArrayList与顺序表
  • SpringBoot之核心配置
  • EasyExcel上传校验文件错误信息放到文件里以Base64 返回给前端
  • 单片机软件定时器V4.0
  • 超完整Docker学习记录,Docker常用命令详解
  • C++ 入门第26天:文件与流操作基础
  • 使用python将多个Excel表合并成一个表
  • halcon三维点云数据处理(七)find_shape_model_3d_recompute_score
  • vue js实现时钟以及刻度效果
  • unity学习15:预制体prefab
  • 基于Thinkphp6+uniapp的陪玩陪聊软件开发方案分析
  • MySQL - 子查询和相关子查询详解
  • Android 系统签名 keytool-importkeypair
  • 安卓漏洞学习(十八):Android加固基本原理
  • Docker 使用Dockerfile创建镜像