python - 88. Merge Sorted Array

问题描述

问 题

leetcode上的这道题：
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.

python的一个解法是：

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        nums1[m:] = nums2[:n]
        nums1.sort()

我就想问问这和下面这个解法意思不是差不多吗？为什么下面这张解法不行？下面这个我在IDE里面运行答案是对的，但是提交答案错了。

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        for x in nums2:
            nums1.append(x)
        nums1.sort()

或者还有一个：

nums1 = nums1+nums2

这种也不行，为什么啊？

刚刚想到，是不是第一种没有操作到nums2，所以不算合并？
然后第二种，我看nums1在外面是没有改变的，为什么会那样？

解决方案

我沒有實際做這題, 我猜測他的意思寫了下面一段代碼, 你應該看了就明白問題在哪:

簡單的測試

def merge1(nums1, m, nums2, n):
    nums1[m:] = nums2[:n]
    nums1.sort()

def merge2(nums1, m, nums2, n):
    for x in nums2:
        nums1.append(x)
    nums1.sort()

def merge3(nums1, m, nums2, n):
    nums1 = nums1 + nums2


m = 3
n = 2

for merge in [merge1, merge2, merge3]:
    nums1 = [1, 5, 8, 0, 0]
    nums2 = [2, 3, 0]
    merge(nums1, m, nums2, n)
    print('{:>8}: {}'.format(merge.__name__, nums1))

結果:

  merge1: [1, 2, 3, 5, 8]
  merge2: [0, 0, 0, 1, 2, 3, 5, 8]
  merge3: [1, 5, 8, 0, 0]

說明

本題對於 Python 來說不是那麼妥當( leetcode 很多資料結構的題目都有這種問題), 原題講的是 array, 但我們這邊操作的是 list, 雖然 Python 的 list 其實比較像是 array 但是還是有些許不同。

由題目可知, nums1 的長度由 m+n 起跳, 這邊可能是弄不清楚的原因, m 表示了元素的數量, m+n 以上說明的是 nums1 的長度(空間), 所以在我的例子中, 我使用 0 代表一個無意義的數字但強調有該空間的存在。

merge1

所以第一種作法, nums1[m:] = nums2[:n] 是將 nums2 的前 n 個元素(有效元素) 填入 nums1 的後半部空間(從第 m+1 個位置開始填), 最後再進行排序, 所以最後的答案會是我們要的。

merge2

第二種作法乍看與第一種作法相同, 但在本題可能會使用的輸入資料而言, 其實並不相同, 他並不會使用 nums1 後面剩餘的空間, 反而對 nums2 中的每個元素都新增了一個空間(使用了 append), 這導致了 nums1 的長度(空間) 改變。

merge3

這種作法的問題跟第二種做法一樣, 但是更嚴重的是, nums1 + nums2 會產生一個新的對象, 因為這個改變並非 in-place 的, 雖然最後依然賦值給 nums1, 但這個變量已經不是參考到原本的 nums1 了, 原本的 nums1 完全沒有受到影響。

希望有正確理解題目並解決你的疑惑!

---

我回答過的問題: Python-QA

这篇关于python - 88. Merge Sorted Array的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！