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 代表一个无意义的数字但强调有该空间的存在。 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

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.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

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

所以你的解法确实是错误的

PS: 不知道是我英语渣还是本来这出题的老外就有点词不达意, 看标准答案的意图是把一个list的前m项和另一个list的后n项合并为新的list并排序, 但题目表达的意思明显就是合并两个list而已, 囧#🎜🎜#