python - 88. Merge Sorted Array

Answer 1

I didn’t actually do this question. I guessed what he meant and wrote the following piece of code. You should understand what the problem is after reading it:

Simple test

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

Result:

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

Instructions

This question is not so appropriate for Python (many data structure questions in leetcode have this problem). The original question is about array, but what we are dealing with here is list. Although Python's list is actually more like array, it is still A little different.

As can be seen from the title, the length (space) of nums1 的長度由 m+n 起跳, 這邊可能是弄不清楚的原因, m 表示了元素的數量, m+n 以上說明的是 nums1, so in my example, I use 0 to represent a meaningless number but emphasize the existence of the space.

merge1

So the first method is to start filling in the nums1[m:] = nums2[:n] 是將 nums2 的前 n 個元素(有效元素) 填入 nums1 的後半部空間(從第 m+1 positions), and finally sort them, so the final answer will be what we want.

merge2

The second method looks the same as the first method at first glance, but in terms of the input data that may be used in this question, it is actually different. It does not use the length (space) of nums1 後面剩餘的空間, 反而對 nums2 中的每個元素都新增了一個空間(使用了 append), 這導致了 nums1 to change.

merge3

The problem with this approach is the same as the second approach, but more seriously, nums1 + nums2 會產生一個新的對象, 因為這個改變並非 in-place 的, 雖然最後依然賦值給 nums1, 但這個變量已經不是參考到原本的 nums1 了, 原本的 nums1 is not affected at all.

Hope you can understand the question correctly and solve your doubts!

---

Questions I answered: Python-QA

Answer 2

You may have misunderstood the meaning of the question

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

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

So your solution is indeed wrong

PS: I don’t know if it’s my poor English or the foreigner who originally asked this question is a bit unclear. The intention of the standard answer is to merge the first m items of one list and the last n items of another list into a new list and sort it. , but the meaning of the title is obviously to merge two lists, 囧