88. Merge Sorted Array

题目描述

给两个有序数组nums1和nums2，长度分别为m和n。假定nums1有足够空间，将nums2合并到nums1中去，使得新的nums1也有序。

我的解法——DP

• 遍历一遍数组，pos[i]代表比nums2中比nums1[i]小的元素的个数，需要做的是在nums1中从后往前将nums2中元素塞进对应位置即可，jj代表nums2中已经塞到nums1中的元素数
• n的复杂度。
• 结果：beat 42.78%

class Solution(object):
    def merge(self, nums1, m, nums2, n):        
        jj = 0  # nums2中已经被安排好的数目，剩余比nums1中最大值还大的数
        pos = [0] * m  #nums2在nums1中被安排的情况
        
        # DP求取
        for i in range(m):
            while(jj < n and nums1[i] >= nums2[jj]):
                pos[i] += 1
                jj += 1
            if(i != 0):
                pos[i] += pos[i - 1]
                
        # 复制最后面的
        for i in range(n - jj):
            nums1[m + n - i - 1] = nums2[n - i - 1]
        
        # 复制前面的 
        for i in range(m - 1,-1,-1):
            # 当前元素前面需要塞几个元素
            if(i != 0):
                nowpos = pos[i] - pos[i - 1]
            else:
                nowpos = pos[i]
                
            # 移动当前nums1的元素
            nums1[i + pos[i]] = nums1[i]
            
            # 往当前元素前塞nums2元素
            for j in range(1,nowpos + 1):
                nums1[i + pos[i] - j] = nums2[jj - 1] 
                jj -= 1

其他解法——利用后n个空闲的空间+反向遍历

• 最好的解法！！！
• 从nums1的最大的元素和nums2的最大的元素开始比较，利用三个指针向前移动
• 注意：merge可能有对不齐的情况，要额外处理一下。
• n的时间复杂度

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i=m-1;
		int j=n-1;
		int k = m+n-1;
		while(i >=0 && j>=0)
		{
			if(A[i] > B[j])
				A[k--] = A[i--];
			else
				A[k--] = B[j--];
		}
		while(j>=0)
			A[k--] = B[j--];
    }
};

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        todo_count = n
        i1 = m - 1
        i2 = n - 1
        while(i2 >= 0 and i1 >= 0):
            if(nums2[i2] >= nums1[i1]):
                nums1[i1 + todo_count] = nums2[i2]
                i2 -= 1
                todo_count -= 1
            else:
                nums1[i1 + todo_count] = nums1[i1]
                i1 -= 1
        while(i2 >= 0):
            nums1[i1 + todo_count] = nums2[i2]
            i2 -= 1
            todo_count -= 1