合并两个有序数组

一觉睡到小时候

发布于 2019-07-03 17:15:24

1.2K0

发布于 2019-07-03 17:15:24

文章被收录于专栏：国产程序员

题目

有两个排序的整数数组，分别是数组1和数组2，将数组2合并到数组1中，合并以后的数组1，仍是有序数组。提示：

数组1有m个元素，数组2有n个元素
可以假设数组1有足够的空间（大于m+n）去容纳从数组2得到的额外的元素。

具体化问题，写出两个有序数组以后，分析问题得出思路。以所给例子作为参考。

思路

思路1：

从前往后构造数组，拿array2中的最前面的元素跟array1中的最前面的元素比较，找到正确的排序以后插入，然后把array1后面的元素都向后移一位。时间复杂度太高。

思路2：

新构造一个空数组array3，那array2中的最前面的元素跟array1中的最前面的元素比较，然后将小的数依次插入到array3后面。这个方法降低了时间复杂度，但是额外构造了一个数组。一般这种合并有序的序列，思路应该都是从后向前合并。

思路3：

提示中已经给出，假设array1有足够的空间了，于是我们不需要额外构造一个数组，并且可以从后面不断地比较元素进行合并。

比较array2与array1中最后面的那个元素，把最大的插入第m+n位
改变数组的索引，再次进行上面的比较，把最大的元素插入到array1中的第m+n-1位。
循环一直到结束。循环结束条件：当index1或index2有一个小于0时，此时就可以结束循环了。如果index2小于0，说明目的达到了。如果index1小于0，就把array2中剩下的前面的元素都复制到array1中去就行。

功能代码

输入一次m>n的情况输入一次m<n的情况

特殊输入情况：

当array1为空，array2不为空时，将array2的所有元素添加到array1中即可
当array1不为空，array2为空时，就是上面的循环结束条件，直接返回array1.
当array1跟array2都为空时，返回空。

我们发现利用index1和index2来做判断以后，实现功能代码的情况下，就能自动满足特殊输入情况了。 Python

①
class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """

        index1 = m - 1
        index2 = n - 1
        #nums1的长度是m+n
        while index2 >= 0:
            if index1 < 0:
                #注意，如果m为0，那么此时index1已经为-1了。执行完下一步就可以跳出循环了。
                #需要break
                nums1[0:index2+1] = nums2[0:index2+1]
                break

            if nums1[index1] >= nums2[index2]:
                nums1[index1 + index2 + 1] = nums1[index1]
                index1 -= 1
            else:
                nums1[index1 + index2 + 1] = nums2[index2]
                index2 -= 1

②
#coding=utf-8
#合并数据
test1 = [1,2,5,7,9]
test2=[2,4,6,8,10,11,34,55]
def mergetest(test1,test2):
  result =[]
  len1=len(test1)
  len2=len(test2)
  i=0
  j=0
  while i<len1 and j<len2:
    if test1[i]<=test2[j]:
      result.append(test1[i])
      i+=1
    else:
      result.append(test2[j])
      j+=1
  if i<len1:
    for z in range(i+1,len1):
      result.append(test1[z])
  elif j<len2:
    for z in range(j+1,len2):
      result.append(test2[z])
  return result
print mergetest(test1,test2)

java

①
public static int[] MergeList(int a[],int b[])
        {
            int result[];  
//                定义一个新数组，长度为两个数组长度之和
                result = new int[a.length+b.length];
              //i:a数组下标    j：b数组下标  k：新数组下标
                int i=0,j=0,k=0;
//                按位循环比较两个数组，较小元素的放入新数组，下标加一（注意，较大元素对应的下标不加一），直到某一个下标等于数组长度时退出循环
                while(i<a.length && j<b.length)
                    if(a[i] <= b[j]) {
                        result[k++] = a[i++];
                        print(result);
                        System.out.println();
                    }else{
                        result[k++] = b[j++];
                    }
                /* 后面连个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利传入 *
                 * 此时较短数组已经全部放入新数组，较长数组还有部分剩余，最后将剩下的部分元素放入新数组，大功告成*/
                while(i < a.length) 
                    result[k++] = a[i++];
                while(j < b.length)
                    result[k++] = b[j++];
                return result;
           }

②
void mergeList(int a[], int aLength, int b[], int bLength, int result[]) {
    int aIndex = 0; // 遍历数组a的下标
    int bIndex = 0; // 遍历数组b的下标
    int i = 0;      // 记录当前存储位置

    while (aIndex < aLength && bIndex < bLength) {
        if (a[aIndex] <= b[bIndex]) {
            result[i] = a[aIndex];
            aIndex++;
        } else {
            result[i] = b[bIndex];
            bIndex++;
        }

        i++;
    }

    // a剩余
    while (aIndex < aLength) {
        result[i] = a[aIndex];
        i++;
        aIndex++;
    }

    // b剩余
    while (bIndex < bLength) {
        result[i] = b[bIndex];
        i++;
        bIndex++;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-04-13，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自国产程序员微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度