合并两个有序数组

Posted on In ,

合并两个有序数组

思路1:最简单的操作是将nums2直接拼在nums1后面，然后对nums1排序
这样的话会用到python自带的排序算法，也可以自己写一下快排代替。总体来讲是先合并再排序。这样的话就没有使用到给出的有序数组中有序的信息。所以复杂度难免会高一点。

1
2
3
4
def merge(nums1, m, nums2, n):
	nums1[m:] = nums2[:n]
	nums1.sort()
	return nums1

思路2:利用有序信息，依次比较插入nums1中，这种复杂度会低一些，但是边界的判断会复杂一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge(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.
    """
    i = m+n-1  # nums1的下标长度
    while(i >= 0):
        if (len(nums1)==0) or (len(nums2)==0):  # 如果有一个数组为空，则直接拼接
            nums1[m:] = nums2
        elif (m == 0):  # 如果nums1已经比较完了，则将nums2的剩余部分赋值到nums1
            nums1[i] = nums2[n-1]
            n = n - 1
        elif (nums1[m-1] >= nums2[n-1]):  # 否则比较两数组最后一个元素大小，将大者放入nums1后，并更新下标
            nums1[i] = nums1[m-1]
            m = m-1
        elif (nums1[m-1] < nums2[n-1]) and (n-1>=0):  # 判断大小并检查nums2是否判断完毕，如果nums2判断完毕，则不再利用nums中值，避免循环引用
            nums1[i] = nums2[n-1]
            n = n-1
        i = i - 1
    return nums1