合并排序数组 II

要求:

合并两个排序的整数数组A和B变成一个新的数组。

样例

给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]

挑战

你能否优化你的算法，如果其中一个数组很大而另一个数组很小？

思路:

两个数组已经排好序,需要考虑的是如何合并能减少复杂度呢?遍历小数组A的每一个数numA(A[j]),若其小于B的numB(B[k]),则将其插入数组B中的k的位置,若numA不小于数组B中任何一个数,则将其放到数组B的最后面.

示例:

def sortedArray(self,A,B):

        len1 = len(A)

        len2 = len(B)

        if len1 <= len2 :

            return (A,B)

        else:

            return (B,A)

    def mergeSortedArray(self,A,B):

        A,B = self.sortedArray(A,B)

        for j,numA in enumerate(A):

            minNum = numA

            count = 0

            for k,numB in enumerate(B):

                count = 0

                if minNum <= numB:

                    B.insert(k, minNum)

                    count += 1

                    break

            if count == 0:

                B.append(minNum)

        return B

耗时: