合并两个有序数组

题目：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

思路：先看num1中第一个与num2最后一个元素的大小；再看num1最后一个与num2第一个打大小。再逐个比较

注：不能额外开辟空间

class :
    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.
        """
        if not nums1 or not nums2:
            nums1[m:n] = nums2[:n]


        else:

            if nums1[m-1] <= nums2[0]:
                nums1[m:n] = nums2[:n]
            elif nums2[n-1] <= nums1[0]:
                nums1 = nums2[:n]
                nums1.extend(nums1[:m])
            else:
                nums1 = nums1[:m]
                nums1.extend(nums2[:n])
                i = 0; j = m+n-1
                while i<=j:
                    if nums1[i] > nums1[j]:
                        nums1[i],nums1[j] = nums1[j],nums1[i]
                    i+=1;j-=1
        return nums1
nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
print(Solution().merge(nums1,3,nums2,3))

合并两个有序数组

近期文章

近期评论

标签

热门

文章归档

分类目录

功能