如何合并两个排序数组？

Question

问题是==

将nums1和nums2合并到一个按非递减顺序排序的数组中。

最终排序的数组不应由函数返回，而应存储在数组 nums1 中。为了适应这种情况，nums1 的长度为 m n，其中前 m 个元素表示应合并的元素，最后 n 个元素设置为 0 并应忽略。nums2 的长度为 n。

我的代码中有什么错误？？？

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = 0; 
        int l = 0;
        for(int i=0; i<(m+n); i++){
            if(k > (m-1)){
                nums1[i] = nums2[l];
                l += 1;
            }
            else if(nums1[k] <= nums2[l]){
                nums1[i] = nums1[k];
                k += 1;
            }
            else {
                nums1[i] = nums2[l];
                l += 1;
            }
        }
    }
}

您的意见

[1,2,3,0,0,0]
3
[2,5,6]
3

我的产出

[1,2,2,2,5,6]

预期产出

[1,2,2,3,5,6]

Answer 1

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        index = 0
        for x in range(len(nums1)):
            if index>=n:
                break
            if nums1[x]==0:
                nums1[x]=nums2[index]
                index+=1
        nums1.sort()

Answer 2

因为在for循环中的if子句中，您基本上将第二个数组放在第一个数组的末尾，而不测试它的数字是否已经被使用。

Answer 3

在合并数组时，您覆盖了nums1中的值，这样，在用nums2中的数字检查它们之前，您替换了nums1中的一些数字。在您的示例中，当您进行合并时，有一个时刻，您有< code>i=2，< code>k=2，< code>l=0，并且您的nums1看起来如下:< code>nums1=[1，2，3，0，0，0]。到目前为止，它看起来不错，但现在您有值为< code>3的< code>nums1[k]和值为< code>2的< code>nums2[l]，因此您要设置< code>nums1[i]=nums2[l]，即< code>nums1[2]=nums2[0]。这样，您就用来自< code>nums2的< code>2替换了< code>nums1中的< code>3,这样您就丢失了来自原始< code>nums1的< code>3,并且无法将其放入最终数组中。

此问题有两种解决方案：

1. 辅助（临时）数组，您将在其中放置数字，最后该数组将被合并并排序为nums1和nums2的数组，因此您可以将该数组复制到nums1中，以便将所有数字合并并排序到nums2中。
2. 每次将nums2中的一个数字放入nums1的i位置时，将所有未处理的数字从原始nums1（从i位置到nums1中最后一个非零数字的数字）向前移动一个位置，以便将 位置中的数字存储在 位置，前一个 i1位置的数字将位于 i2位置等。只需保持移动这些数字的正确顺序，即从最后一个非零数字开始移动，然后返回，以避免在此过程中丢失任何数字

这些解决方案中的每一个都有自己与时间和空间复杂度相关的优点和缺点，但作为一个示例，我将展示如何实现第一种方法：

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] mergedAndSortedArray = new int[m + n];
    int k = 0;
    int l = 0;
    for(int i=0; i<(m+n); i++){
        if(k > (m-1)){
            mergedAndSortedArray[i] = nums2[l];
            l += 1;
        }
        else if(nums1[k] <= nums2[l]){
            mergedAndSortedArray[i] = nums1[k];
            k += 1;
        }
        else {
            mergedAndSortedArray[i] = nums2[l];
            l += 1;
        }
    }

    // copy final merged and sorted array to nums1, you can also do this using `for` loop but this is more efficient way
    System.arraycopy(mergedAndSortedArray, 0, nums1, 0, m + n);
}