java 如何合并两个排序数组?

rm5edbpk  于 2023-06-20  发布在  Java
关注(0)|答案(5)|浏览(164)

问题是==>你有两个整数数组nums1和nums2,按非降序排序,还有两个整数m和n,分别表示nums1和nums2中的元素数量。
将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]
lb3vh1jj

lb3vh1jj1#

在合并数组时覆盖了nums1中的值,这样,在用nums2中的数字检查nums1中的一些数字之前,就替换了它们。在你的例子中,当你合并的时候,有一个时刻,你有i=2k=2l=0和你的nums1看起来如下:nums1=[1,2,3,0,0,0]。到目前为止,它看起来不错,但现在你有值为3nums1[k]和值为2nums2[l],所以你设置了nums1[i]=nums2[l],即nums1[2]=nums2[0]。这样你就用nums2中的2替换了nums1中的3,这样你就失去了原来nums1中的3,你就不能把它放在最终的数组中了。
此问题有两种解决方案:
1.辅助(临时)数组,您将在其中放置数字,最后此数组将合并并排序nums1和nums2的数组,因此您可以将此数组复制到nums1中,以便在nums1中合并并排序所有数字。
1.每次将nums2中的数字放入nums1中的i位置时,将所有未处理的数字从原始nums1中移出(从i位置到nums1中最后一个非零数字的数字)向前移动一个位置,以便您从i位置开始的数字将存储在i+1位置,从先前i+1位置开始的数字将在i+2位置,依此类推。只要保持移动这些数字的正确顺序,即。从最后一个非零数字开始移动它们,并返回以避免在此过程中丢失任何数字。
这些解决方案中的每一种都有其自身的与时间和空间复杂度相关的优点和缺点,但作为示例,我将展示如何实现第一种方法:

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

f45qwnt82#

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

rqenqsqc

rqenqsqc3#

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()
kuhbmx9i

kuhbmx9i4#

JavaScript解决方案:

var merge = function(nums1, m, nums2, n) {
  let num1Length = m-1;
  let num2Length = n-1;
  
  for(let i=nums1.length-1; i>=0; i--){
      if(nums1[num1Length]>=nums2[num2Length]){
          nums1[i] = nums1[num1Length];
          num1Length--;
      }else if(num2Length>=0){
          nums1[i] = nums2[num2Length];
          num2Length--;
      }
  }
};

const nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);
l2osamch

l2osamch5#

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

相关问题