leetcode88-- Merge Sorted Array

leetcode88-- Merge Sorted Array

即给定两个已经排好序的数组,求他们 合并之后的数组,其中合并之后的也是排好序的

代码要求不需要有返回值,直接在nums1上进行replace

idea1

把nums1 深copy一份,注意不能直接简单的等于,不然会错的,需要这样ret[:] = nums1

然后依次比较ret和nums2的最前面的元素,用过了的就进一,

结果如下

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.
        """
        if m == 0:
            nums1[:] = nums2
            return
        if n==0:
            return 
        
        ret = []
        ret[:] = nums1  #相当于nums1的一个深copy.
        
        i,j = 0,0
        
        for k in range(m+n):   ## 也可以用一个while来写.
            minimum = min(ret[i], nums2[j])
            nums1[k] = minimum
        
            
            if minimum == ret[i]:
                i += 1
                if i>=m:
                    nums1[k+1:m+n] = nums2[j:n]  ##这时候用的一定是ret[i],所以nums2[j]还没有被用.
                
                    return
            else:
                j += 1
                if j>=n:
                    nums1[k+1:m+n] = ret[i:m]
                    
                    return 
            

其中当m=0的那里nums1[:] = nums2如果改成nums1=nums2的话也会报错。

还可以改成下面的用while

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.
        """
        if m == 0:
            nums1[:] = nums2
            return
        if n==0:
            return 
        
        ret = []
        ret[:] = nums1  #相当于nums1的一个深copy.
        
        i,j = 0,0
        k = 0
        while i<m and j<n:
            minimum = min(ret[i], nums2[j])
            nums1[k]= minimum
            
            if minimum == ret[i]:
                i += 1
            else:
                j += 1
            k += 1
            
        # 上面break的时候新的k(是上面的加了1之后的)还没有填.
        if i == m:
            nums1[k:m+n] = nums2[j:n]
        else:
            nums1[k:m+n] = ret[i:m]
            

如果不要求用其他的新的东西的话,比如上面的ret,直接在nums1修改的话,应该从后面大的部分开始

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.
        """
        if m == 0:
            nums1[:] = nums2
            return
        if n==0:
            return 
        
        i = m-1
        j = n-1
        k = m+n-1
        
        while i>=0 and j>=0:
            maximum= max(nums1[i], nums2[j])
            nums1[k] = maximum
            k -= 1
            
            if maximum == nums1[i]:
                i -= 1
            else:
                j -= 1
                
        if i<0: #说明第一个的所有的都用完了,需要把num2的补到nums1的前面去
            nums1[:(k+1)] = nums2[:(j+1)]   # 因为不包含最后一个的,所以要加1.
        else:
            nums1[:(k+1)] = nums1[:(i+1)]
            
            

还可以下面这样

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 不申请新的空间的话应该从后面的大的地方开始
        i = m-1
        j = n-1
        k = m+n-1
        
        # 上面分别代表第一个数组,第二个数组,和混合之后的数组的末尾
        
        while i>=0 and j>=0:
            if nums1[i]> nums2[j]:
                nums1[k] = nums1[i]
                k -= 1
                i -= 1
            else:
                nums1[k] = nums2[j]
                k -= 1
                j -= 1
        # 说明其中一个用完了
        # 当i>=0的时候没有关系
        # 当j>=0的时候
        while j>=0:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1
            
        

还可以改成


还可以改成

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: “”” Do not return anything, modify nums1 in-place instead. “”” # 不申请新的空间的话应该从后面的大的地方开始 i = m-1 j = n-1 k = m+n-1

    # 上面分别代表第一个数组,第二个数组,和混合之后的数组的末尾
    
    while j>=0:
        if nums1[i]> nums2[j] and i>=0:
            nums1[k] = nums1[i]
            k -= 1
            i -= 1
        else:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1

```

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦