欢迎访问宙启技术站
智能推送

如何使用Java编写一个函数来合并两个有序数组为一个有序数组?

发布时间:2023-12-08 17:39:15

要合并两个有序数组为一个有序数组,可以使用双指针的方法进行合并。具体步骤如下:

1. 新建一个长度为两个数组长度之和的结果数组。

2. 初始化三个指针:一个指向第一个数组的开头,另一个指向第二个数组的开头,第三个指向结果数组的开头。

3. 使用循环来比较两个指针所指向的数值大小,将较小的数值复制到结果数组中,并移动对应的指针以继续比较。

4. 当其中一个数组的指针移动到末尾时,将另一个数组剩余部分依次拷贝到结果数组的末尾。

5. 返回合并后的结果数组。

代码示例:

public class MergeSortedArrays {
    
    public static int[] mergeArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        
        while (i < nums1.length) {
            merged[k++] = nums1[i++];
        }
        
        while (j < nums2.length) {
            merged[k++] = nums2[j++];
        }
        
        return merged;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5};
        int[] nums2 = {2, 4, 6};
        
        int[] merged = mergeArrays(nums1, nums2);
        
        for (int num : merged) {
            System.out.print(num + " ");
        }
    }
}

运行这段代码,输出为:1 2 3 4 5 6,即两个有序数组合并后的结果。

这个方法的时间复杂度是O(n),其中n是两个数组的长度之和,因为需要通过循环遍历两个数组中的所有元素来进行合并。