python - 88. Merge Sorted Array

Answer 1

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

簡單的測試

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

Answer 2

你可能是理解錯題意了

You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

這段提示的意思是len(nums1) >= m + n, 具体说就是你需要把 nums1 的前 m 项和 nums2 的后 n 项合并成为一个新的 array(list) 并对其进行排序(nums1的元素个数不低于m + n)

所以你的解法確實是錯誤的

PS: 不知道是我英語渣還是本來這出題的老外就有點詞不達意, 看標準答案的意圖是把一個list的前m項和另一個list的後n項合併為新的list並排序, 但題目表達的意思明顯就是合併兩個list而已, 囧