在Java中合并两个排序的数组 [英] Merge two sorted arrays in java

问题描述

我知道有人问过类似的问题，并且我已经进行了研究许多网站.我尝试使用一些答案，但是我的代码是仍然无法正常工作.

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.

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

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.

这是我的问题:

实施一种方法合并，该方法将给定两个已排序的整数元素数组，并返回一个包含两个输入数组的所有元素的新的已排序数组.

Implement a method merge that, given two arrays of sorted integer elements, returns a new sorted array with all the elements of the two input arrays.

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

Assume that the elements in both input arrays are sorted in non-decreasing order (e.g. [0, 1, 2, 2] and [1, 2, 3, 3, 4, 5]). The returned "merged" array must keep this property (e.g. [0, 1, 1, 2, 2, 2, 3, 3, 4, 5]).

输入和输出中均允许重复.

Duplicates are allowed in both the input and the output.

如果其中一个数组为null，则将非null数组作为副本返回；如果两个数组均为null，则结果也应为null.

If either one of the arrays are null, return the non-null array as a copy, if both arrays are null, the result should be null as well.

效率要求:阵列应在阵列上一次通过合并.

Efficiency requirement: the arrays should be merged in a single pass over the arrays.

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

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;

    }
}

推荐答案

在Internet上的多个地方对此都有很好的解释.看看 Java程序可以合并两个排序的数组，其中显示了该算法的图形说明.您可以将方法更改为使用单个 while 循环，如下所示:

This is well explained in multiple places on the Internet. Take a look at Java program to merge two sorted arrays which showes a graphical explanation of the algorithm. You can change your method to use a single while loop as:

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;
}

这篇关于在Java中合并两个排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！