88、合并两个有序数组

LeetCode--88

一、题目

有两个排序的整数数组,分别是数组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来做判断以后,实现功能代码的情况下,就能自动满足特殊输入情况了。

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
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容