Java数组拼接两种实现的内存占用及复杂度差异疑问

问题描述 #

给定长度为n的整数数组nums，需生成长度为2n的数组ans，满足ans[i] == nums[i]且ans[i+n] == nums[i]（0 ≤ i < n，0索引），即ans是nums的两次拼接。
示例：输入nums = [1,2,1]，输出ans = [1,2,1,1,2,1]。

本人编写了两种Java实现方案，代码1运行内存为44.42MB，代码2为44.72MB。无法理解为何代码1的空间复杂度及时间复杂度优于代码2，请求解释两者的内存占用差异及复杂度优劣原因。

实现代码 #

代码1 #

class Solution {
public int[] getConcatenation(int[] nums) {

 int n = nums.length;
 int[] arr = new int[2*n];
 int k = 0;
 int count = 0;
 for(int i = 0; i < n; i++){
     arr[k] = nums[i];
     k++;
     if(i == n-1){
         i = -1;
         count++;
     }
     if(count == 2){
         break;
     }
 }
 
return arr;
}
}

代码2 #

class Solution {
 public int[] getConcatenation(int[] nums) {

 int n = nums.length;
 int[] arr = new int[2*n];
 
 for(int i = 0; i < 2*n; i++){
     arr[i] = nums[i % n];
 }
 
return arr;
}
}

差异解析 #

时间复杂度 #

两种代码的时间复杂度完全一致，都是O(n)。两者都需要完成2n次元素赋值操作，执行的总操作次数是线性的，不存在优劣之分。你觉得代码1时间更优是误解，实际两者的时间效率本质等价。

空间复杂度 #

两者的空间复杂度同样一致，都是O(n)。核心原因是它们都创建了一个长度为2n的结果数组，这是主要的空间开销；代码1额外的k、count两个int变量属于常数级空间占用（O(1)），对整体空间复杂度没有影响。

内存占用细微差异的原因 #

出现0.3MB的内存差异属于测试环境的正常波动，同时也和代码的执行细节有关：

• 取模操作的额外开销：代码2的循环中每次都要执行i % n取模运算，这个操作比单纯的数组索引访问需要更多的CPU指令和临时存储，JVM运行时可能会为其分配额外的寄存器或栈空间，导致内存占用略有上升。
• JVM优化策略差异：代码1的循环是通过重置i实现两次遍历，逻辑更直接，JVM可能对这种连续的数组拷贝做了更高效的优化；而代码2的取模操作属于相对复杂的运算，JVM的优化程度稍低，进而导致内存占用略高。
• 测试误差：在线判题平台的内存统计存在一定随机性，多次运行同一代码的结果也可能有细微波动，0.3MB的差异不足以说明代码本身的空间效率有优劣。

内容的提问来源于stack exchange，提问作者Shantanu Patil