You need to enable JavaScript to run this app. 咨询gfg平台两数组求并集Java代码的空间复杂度判定
优惠活动
大模型
产品
解决方案
定价
更多

咨询gfg平台两数组求并集Java代码的空间复杂度判定

空间复杂度逐模块拆解

很多人算这段代码的空间复杂度时,容易把输入读取的临时开销和算法核心的辅助空间混在一起,我们直接把所有内存占用的模块拆开算就清楚了:

  • 核心算法依赖的存储结构:你用来存并集元素的HashSet。最坏情况下两个输入数组完全没有重复元素,这个集合需要存放N+M个Integer对象,这部分的内存增长完全和两个数组的总长度呈线性正相关,量级就是O(N+M),刚好匹配题目给出的预期辅助空间复杂度。
  • 输入读取环节的临时结构:代码里的BufferedReader、三个用来存分割后字符串的数组(input/inp1/inp2)。
    • 其中BufferedReader的缓冲区是固定大小的,和输入数组的长度、测试用例数量完全无关,属于常量级的固定开销,算O(1)的基础运行成本。
    • 那三个字符串数组的长度,本身就和两个输入数组的长度一一对应,本质是输入数据的临时载体,不是算法为了计算额外申请的冗余存储。而且这些数组在把元素转成整数加入Set之后,就会变成可被GC回收的对象,不会长期占用线性规模的内存。

这里要明确OJ题目标注的辅助空间复杂度的统计口径:它只计算「算法为了完成核心计算逻辑,和输入规模正相关的非输入类存储」,不会把程序运行的固定基础开销、输入流转过程中的临时载体内存全部算成算法的额外空间。

最终复杂度结论
  1. 这段代码的核心算法辅助空间复杂度确实是O(N+M),完全符合题目的预期要求。哪怕把所有输入临时结构的内存算上,整体内存占用的上界也还是O(N+M)——因为没有任何额外申请的、超过线性量级的存储结构,不存在复杂度超标的问题。
  2. 你之前的困惑大概率来自于输入逻辑引入的几个临时字符串数组带来的视觉上的“额外内存”,实际上这些临时结构的内存规模和输入长度严格线性对应,既不会拉高整体的复杂度量级,也不属于核心算法需要承担的辅助空间成本。

如果想要进一步压缩输入环节的临时内存,完全可以用StreamTokenizer逐值读取输入,不用一次性把整行输入split成字符串数组,不过这种优化只会降低常数级的内存占用,不会改变整体的复杂度量级。


内容的提问来源于stack exchange,提问作者TANESH GUPTA

相关产品推荐
方舟 Agent Plan

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

最近更新时间:2026.11.16 00:45:01