【LeetCode with Python】 88. Merge Sorted Array

题目

原题页面:https://leetcode.com/problems/merge-sorted-array/
本文地址:http://leetcode.xnerv.wang/merge-sorted-array/
题目类型:Array, Two Pointers
难度评价:Easy
类似题目:(E) Merge Two Sorted Lists

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is > greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.


分析

将一个有序数组B合并到另一个有序数组A。这题如果从数组头开始合并,则每一次都要整体移动数组A后面的元素,显然不是理想的方法。一种巧妙的做法是从两个数组尾部开始合并,这样就避免了大面积的数组元素移动


代码

class Solution:
    # @param A  a list of integers
    # @param m  an integer, length of A
    # @param B  a list of integers
    # @param n  an integer, length of B
    # @return nothing
    def merge(self, A, m, B, n):
        if 0 == n:
            return A
        if 0 == m:
            for i in range(0, n):
                A[i] = B[i]
            return A

        index = m + n - 1
        indexA = m - 1
        indexB = n - 1
        while indexA >= 0 and indexB >= 0:
            if A[indexA] >= B[indexB]:
                A[index] = A[indexA]
                index -= 1
                indexA -= 1
            else:
                A[index] = B[indexB]
                index -= 1
                indexB -= 1
        if indexA >= 0:
            pass
        else:
            for i in range(0, indexB + 1):
                A[i] = B[i]

results matching ""

    No results matching ""