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

Question

\n

我知道有人问过类似的问题，并且我研究过许多网站。我尝试使用一些答案，但我的代码\n仍然无法工作。

\n\n

我正在完成之前的作业，以帮助积累我的 Java 知识。请原谅我的代码中的任何错误，我仍在学习 Java。

\n\n

这是我的问题：

\n

\n\n

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

\n\n

假设两个输入数组中的元素均按非降序排序（例如 [0, 1, 2, 2] 和 [1, 2, 3, 3, 4, 5]）。返回的 \xe2\x80\x9cmerged\xe2\x80\x9d 数组必须保留此属性（例如 [0, 1, 1, 2, 2, 2, 3, 3, 4, 5]）。

\n\n

输入和输出都允许重复。

\n\n

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

\n\n

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

\n\n

\n

这是我到目前为止所做的，它不符合要求，所以我需要帮助才能找到正确的解决方案：

\n

\n\n

public class MergeArray {\n    public static int[] merge(int[] arr1, int[] arr2) {\n        if (arr1 == null && arr2 == null) {\n            return null;\n        }\n        if (arr1 != null & arr2 == null) {\n            return arr1;\n        }\n        if (arr2 != null & arr1 == null) {\n            return arr2;\n        }\n        int[] merged = new int [arr1.length+arr2.length];\n\n        if (arr1.length > arr2.length) {\n            for (int i = 0; i < arr1.length; i++) {\n\n                if (arr1[i] <= arr2[i]) {\n                    merged[i] = arr1[i];\n                    merged[i + 1] = arr2[i];\n                }\n                if (arr2[i] < arr1[i]) {\n                    merged[i] = arr2[i];\n                    merged[i + 1] = arr1[i];\n                }\n            }\n            if (arr1.length < arr2.length) {\n                for (int i = 0; i < arr2.length; i++) {\n\n                    if (arr1[i] <= arr2[i]) {\n                        merged[i] = arr1[i];\n                        merged[i + 1] = arr2[i];\n                    }\n                    if (arr2[i] < arr1[i]) {\n                        merged[i] = arr2[i];\n                        merged[i + 1] = arr1[i];\n                    }\n                }\n\n            }\n\n        }\n        return merged;\n\n    }\n}\n

\n

Answer 1

互联网上的多个地方对此都有很好的解释。看一下合并两个排序数组的 Java 程序，其中显示了该算法的图形解释。您可以更改方法以使用单个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;
}