java - java中合并两个已排序的数组

Question

I know that similar questions have been asked and I have researched many websites. I have tried to use some of the answers but my code is still not working.

I am going through a previous assignments to help build my knowledge of Java. Please forgive any errors in my code, I am still learning Java.

Here is my question:

实现一个 merge 方法，给定两个已排序整数元素数组，返回一个新的已排序数组，其中包含两个输入数组的所有元素。

假设两个输入数组中的元素均按非降序排序(例如 [0, 1, 2, 2] 和 [1, 2, 3, 3, 4, 5])。返回的“合并”数组必须保留此属性(例如 [0, 1, 1, 2, 2, 2, 3, 3, 4, 5])。

输入和输出都允许重复。

如果其中一个数组为 null，则返回非 null 数组作为副本，如果两个数组都为 null，则结果也应该为 null。

效率要求:数组应在一次遍历数组中合并。

Here is what I've done so far, it doesn't meet the requirements so I need help in order to find the right solution:

public class MergeArray {
    public static int[] merge(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return null;
        }
        if (arr1 != null & arr2 == null) {
            return arr1;
        }
        if (arr2 != null & arr1 == null) {
            return arr2;
        }
        int[] merged = new int [arr1.length+arr2.length];

        if (arr1.length > arr2.length) {
            for (int i = 0; i < arr1.length; i++) {

                if (arr1[i] <= arr2[i]) {
                    merged[i] = arr1[i];
                    merged[i + 1] = arr2[i];
                }
                if (arr2[i] < arr1[i]) {
                    merged[i] = arr2[i];
                    merged[i + 1] = arr1[i];
                }
            }
            if (arr1.length < arr2.length) {
                for (int i = 0; i < arr2.length; i++) {

                    if (arr1[i] <= arr2[i]) {
                        merged[i] = arr1[i];
                        merged[i + 1] = arr2[i];
                    }
                    if (arr2[i] < arr1[i]) {
                        merged[i] = arr2[i];
                        merged[i + 1] = arr1[i];
                    }
                }

            }

        }
        return merged;

    }
}

Answer 1

互联网上的多个地方对此都有很好的解释。看看Java program to merge two sorted arrays它显示了算法的图形解释。您可以更改方法以使用单个 while 循环:

public static int[] merge(int[] arr1, int[] arr2) {
  if (arr1 == null && arr2 == null) return null;
  if (arr1 == null) return arr2.clone();
  if (arr2 == null) return arr1.clone();       

  int[] result = new int[arr1.length + arr2.length];
  int i = 0, j = 0, r = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result[r] = arr1[i];
      i++;
    } else {
      result[r] = arr2[j];
      j++;
    }
    r++;
  }
  // Copy the remaining elements in array 1 to result
  if (i < arr1.length) {
    System.arraycopy(arr1, i, result, r, (arr1.length - i));
  }
  // Copy the remaining elements in array 2 to result
  if (j < arr2.length) {
    System.arraycopy(arr2, j, result, r, (arr2.length - j));
  }
  return result;
}