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

力扣349 == 两个数组交集的两种解法

目录

解法一:利用 Set 特性高效去重

解法二:双重遍历与 Set 去重

方法对比与总结

关键点总结


题目描述
给定两个整数数组 nums1 和 nums2,要求返回它们的交集。输出结果中的每个元素必须是唯一的,且顺序不限。

示例

  • 输入:nums1 = [1,2,2,1], nums2 = [2,2]
    输出:[2]

  • 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出:[9,4] 或 [4,9]


解法一:利用 Set 特性高效去重

思路

  1. 将 nums1 转换为 Set 结构,自动去重。

  2. 遍历 nums2,检查元素是否存在于 Set 中:

    • 若存在,则将该元素加入结果数组,并从 Set 中删除,避免后续重复匹配。

  3. 最终返回结果数组。

代码实现

var intersection = function(nums1, nums2) {const st = new Set(nums1);const ans = [];for (const x of nums2) {if (st.delete(x)) { // 如果元素存在,删除并收集ans.push(x);}}return ans;
};

复杂度分析

  • 时间复杂度:O(m + n),其中 m 和 n 是数组长度。
    转换 nums1 为 Set 需要 O(m),遍历 nums2 需要 O(n)。

  • 空间复杂度:O(m),用于存储 Set

优势

  • 高效处理重复元素:通过 st.delete(x) 确保每个元素只匹配一次。

  • 线性时间复杂度,适合处理大数据量。


解法二:双重遍历与 Set 去重

思路

  1. 遍历 nums1,对每个元素检查是否存在于 nums2 中。

  2. 若存在,则将其加入 Set 自动去重。

  3. 最终将 Set 转为数组返回。

代码实现

var intersection = function(nums1, nums2) {let set = new Set();for (let i = 0; i < nums1.length; i++) {if (nums2.includes(nums1[i])) {set.add(nums1[i]);}}return Array.from(set);
};

复杂度分析

  • 时间复杂度:O(m × n),最坏情况下需遍历 nums2 的每个元素。

  • 空间复杂度:O(k),k 为交集元素的数量。

缺点

  • nums2.includes() 的时间复杂度为 O(n),当数组较大时性能较差。


方法对比与总结

特性解法一(Set + 删除)解法二(双重遍历 + Set)
时间复杂度O(m + n)O(m × n)
空间复杂度O(m)O(k)
处理重复元素立即删除,避免重复匹配依赖 Set 去重
适用场景大数据量小数据量或简单场景

推荐解法
优先选择解法一,因为它利用 Set 的高效查找和删除操作,时间复杂度更低,尤其适合处理大规模数据。解法二虽然代码更直观,但性能较差,仅在数据量较小时适用。


关键点总结

  1. 去重机制:使用 Set 结构天然去重。

  2. 性能优化:通过删除已匹配元素减少重复检查。

  3. 方法选择:根据数据规模选择时间复杂度更优的解法。

http://www.xdnf.cn/news/3205.html

相关文章:

  • selenium 实现模拟登录中的滑块验证功能
  • 【文献笔记】LLM-based control code generation using image recognition
  • 详细讲解一下Java中的Enum
  • Missashe考研日记-day22
  • AI与物联网的深度融合:开启智能生活新时代
  • 写书的三驾马车
  • 【Unity】UI点击事件处理器
  • 文件系统 软硬连接
  • 类和对象(下篇)(详解)
  • 2025.4.20机器学习笔记:文献阅读
  • 【前端】跟着maxkb学习流程图画法
  • Qt QML实现Windows桌面歌词动态播放效果
  • Win10如何一键切换IP地址教程
  • ubtuntu安装docker拉取iwebsec镜像
  • 关于STM32G030和G070未初始化看门狗,程序里面喂狗会导致擦除Flash失败或进入‘HardFault_Handler’
  • WebSocket 实现数据实时推送原理
  • GPT,Bert类模型对比
  • 4.17---实现商铺和缓存与数据库双写一致以及宕机处理
  • 2025.04.17【Dendrogram】生信数据可视化:Dendrogram图表详解
  • 网络编程 - 1
  • Genspark:重新定义AI搜索与代理的全能型工具
  • 私人笔记:动手学大模型应用开发llm-universe项目环境创建
  • 【前端vue生成二维码和条形码——MQ】
  • 【随身WIFI】随身WiFi Debian系统优化教程
  • AUTOSAR图解==>AUTOSAR_SWS_DefaultErrorTracer
  • 计算机网络 - UDP协议
  • 4.15BUUCTF Ez_bypass,HardSQL,AreUSerialz,BabyUpload,CheckIn
  • 【Docker】运行错误提示 unknown shorthand flag: ‘d‘ in -d ----详细解决方法
  • jQuery入门和选择器
  • JavaScript-立即执行函数(Immediately Invoked Function Expression,IIFE)