提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

合并两个有序数组

2023-02-18 16:36:15 时间

题目：

思路：

解法有两种：
1，顺序排序，需要额外创建一个数组大小为m+n，然后比较A与B，遍历填充进新数组。然后把数组再次填充回A里面，所以次数为2*（m+n），当m+n趋于无穷大时，2就被忽略了，时间复杂度为O（m+n），空间复杂度为O(m+n)
2，对于第一种方法如果要优化的点可以从空间开始，因为题目本身就是给予了A足够大的空间，其次是多次额外的赋值对于操作来说也是浪费，所以可以考虑倒序排序的思路。
这种方法的时间复杂度为O（m+n），空间复杂度为O(1)。
 

代码示例：

import java.util.Arrays;
public class Solution {
    public static void main(String[] args) {
        int[] arr1 = new int[20];
        int[] arr2 = new int[10];
        int k = 0;
        for (int i = 0; i < 20; i++) {
            if (i % 2 == 0) {
                arr1[i / 2] = i;
            } else {
                arr2[i / 2] = i;
            }
        }
//        System.out.println(Arrays.toString(arr1));
//        System.out.println(Arrays.toString(arr2));
        int n = arr2.length;
        int m = arr1.length - n;
        merge(arr1, m, arr2, n);
        System.out.println(Arrays.toString(arr1));
    }
    
    /**
    * 为什么是从倒序开始呢？因为从前面开始排，你比对完后占了位置，其他数就要往后面移动，这样操作太大
    * 而且从前文可知A的大小足够容纳两个数组的数，所以从后面按大到小进行排序，这样不会造成其他数因为某个数而需要往后靠的操作
    * 同理需要注意的是下面缺少了对a的继续遍历，因为A数组本身就是有序的，所以如果第一个循环中把a遍历到了最小值，此时要把b继续遍历完
    * 而如果b遍历完了，那么a大可不必遍历，因为本身有序，且是在A里面
    */
    public static void merge(int A[], int m, int B[], int n) {
        int a = m - 1;
        int b = n - 1;
        int k = m + n - 1;
        while (a >= 0 && b >= 0) {
            A[k--] = A[a] > B[b] ? A[a--] : B[b--];
        }
        while (b >= 0) {
            A[k--] = B[b--];
        }
    }
}

相关文章