为何这段合并有序数组的Java代码会出现超时错误？

我正在解决这个问题：给定两个非降序排列的有序数组arr1[]和arr2[]，长度分别为n和m。任务是将这两个数组合并为一个非降序的有序数组，要求不能使用额外空间，期望时间复杂度为O((n+m) log(n+m))。

我写了一份时间复杂度为O(n log m)的代码，但提交后出现了超时错误，想请教问题出在哪里？

附上我的代码：

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int len1 = Integer.parseInt(st.nextToken());
            int len2 = Integer.parseInt(st.nextToken());
            int[] nums1 = new int[len1];
            int[] nums2 = new int[len2];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i<len1; i++)
                nums1[i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i<len2; i++)
                nums2[i] = Integer.parseInt(st.nextToken());
            int temp;
            for(int i =0; i<len1; i++){
                if (nums1[i] > nums2[0]){
                    temp = nums1[i];
                    nums1[i] = nums2[0];
                    nums2[0] = temp;
                    Heapify(nums2,0,len2);
                }
            }
            for(int i = 0; i<len1; i++)
                System.out.print(nums1[i]+" ");
            Arrays.sort(nums2);
            for(int i = 0; i<len2; i++)
                System.out.print(nums2[i]+" ");
            System.out.println();
        }
    }
    static void Heapify(int[] nums, int i, int len){
        int l = 2 * i+1;
        int r = 2 * i + 2;
        int smallest = i;
        if (l < len && nums[l] < nums[i] ){
            smallest = l;
        }
        if (r < len && nums[r] < nums[smallest] ){
            smallest = r;
        }
        if (smallest != i){
            int temp = nums[i];
            nums[i] = nums[smallest];
            nums[smallest] = temp;
            Heapify(nums,smallest,len);
        }
    }
}

问题分析 #

你的代码思路是可行的：遍历nums1的每个元素，若它比nums2的最小元素（小顶堆堆顶）大，则交换两者，再重新堆化nums2维持小顶堆性质；最后排序nums2并输出两个数组。但超时的核心原因有两个：

1. 递归Heapify的额外开销

你的Heapify是递归实现的，每次堆化都会产生函数调用栈的开销。当m很大时（比如1e5级别），递归深度可达log2(m)（约17层），大量递归调用累积的时间消耗是超时的关键因素之一。

2. 实际运行的常数因子过高

虽然理论上你的代码时间复杂度O(n log m + m log m)和题目要求的O((n+m)log(n+m))是同阶的，但堆化操作的常数因子远高于Java内置的Arrays.sort（它是优化过的双枢轴快排）。加上每次交换后的堆化操作，整体实际运行时间会远超预期，在严格的时间限制下容易超时。

解决方案 #

方案一：将递归Heapify改为迭代实现

把递归堆化改成迭代版本，消除函数调用的开销，能显著提升运行速度：

static void Heapify(int[] nums, int i, int len) {
    while (true) {
        int smallest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        
        if (l < len && nums[l] < nums[smallest]) {
            smallest = l;
        }
        if (r < len && nums[r] < nums[smallest]) {
            smallest = r;
        }
        
        if (smallest == i) {
            break;
        }
        
        // 交换当前节点与最小子节点
        int temp = nums[i];
        nums[i] = nums[smallest];
        nums[smallest] = temp;
        
        i = smallest;
    }
}

方案二：使用更高效的原地合并算法（间隙法）

如果迭代堆化后仍然超时，可以尝试间隙排序法（Gap Sort），这是专门针对原地合并两个有序数组的高效算法，时间复杂度为O((n+m)log(n+m))，且常数因子更低：

思路是：

• 计算初始间隙gap = ceil((n + m) / 2)
• 每次将间隙减半，直到gap为0
• 遍历两个数组，比较i和i+gap位置的元素（注意跨数组的边界处理），若前者大于后者则交换

示例代码：

public static void merge(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int totalLen = n + m;
    int gap = (totalLen + 1) / 2; // 初始间隙，向上取整
    
    while (gap > 0) {
        // 处理nums1内部的元素
        int i = 0;
        while (i + gap < n) {
            if (nums1[i] > nums1[i + gap]) {
                swap(nums1, i, i + gap);
            }
            i++;
        }
        
        // 处理跨nums1和nums2的元素
        int j = gap > n ? gap - n : 0;
        while (i < n && j < m) {
            if (nums1[i] > nums2[j]) {
                int temp = nums1[i];
                nums1[i] = nums2[j];
                nums2[j] = temp;
            }
            i++;
            j++;
        }
        
        // 处理nums2内部的元素
        if (j < m) {
            j = 0;
            while (j + gap < m) {
                if (nums2[j] > nums2[j + gap]) {
                    swap(nums2, j, j + gap);
                }
                j++;
            }
        }
        
        gap = gap / 2; // 间隙减半
    }
}

private static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

在主函数中调用merge方法后，直接输出nums1和nums2即可，无需再排序nums2。

内容的提问来源于stack exchange，提问作者Ahad Afzal