python - 88. Merge Sorted Array

Answer 1

Saya sebenarnya tidak melakukan soalan ini, saya meneka apa yang dia maksudkan dan menulis sekeping kod berikut. Anda harus memahami masalahnya selepas membacanya:

Ujian mudah

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

Keputusan:

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

Penerangan

Soalan ini tidak begitu sesuai untuk Python (banyak soalan struktur data dalam leetcode mempunyai masalah ini, soalan asal bercakap tentang tatasusunan, tetapi apa yang kita hadapi di sini ialah senarai, walaupun senarai Python sebenarnya lebih seperti tatasusunan Tetapi ada). masih terdapat beberapa perbezaan.

Seperti yang dapat dilihat dari tajuk, panjang nums1 bermula dari m+n Ini mungkin disebabkan oleh sebab yang tidak jelas m mewakili bilangan elemen m+n Penerangan di atas adalah panjang nums1 ( ruang), jadi dalam contoh saya, saya menggunakan 0 untuk mewakili nombor yang tidak bermakna tetapi untuk menekankan kewujudan ruang.

gabung1

Jadi kaedah pertama, nums1[m:] = nums2[:n] ialah mengisi n elemen pertama (elemen sah) nums2 ke dalam separuh kedua ruang nums1 (bermula dari m+1kedudukan ke-), dan akhirnya Isih mereka supaya jawapan akhir akan menjadi apa yang kita mahu.

gabung2

Kaedah kedua kelihatan sama dengan kaedah pertama pada pandangan pertama, tetapi dari segi data input yang mungkin digunakan dalam soalan ini, ia sebenarnya tidak akan menggunakan ruang yang tinggal selepas nums1, tetapi akan menggunakan menambah ruang baharu (menggunakan nums2), yang menyebabkan panjang (ruang) append berubah. nums1

gabung3

Masalah dengan pendekatan ini adalah sama seperti pendekatan kedua, tetapi lebih serius,

akan menjana objek baharu, kerana perubahan ini tidak berada di tempatnya Walaupun ia masih diberikan kepada nums1 + nums2 pada akhirnya , Pembolehubah ini tidak lagi merujuk kepada nums1 asal, dan nums1 asal tidak terjejas sama sekali. nums1

Saya harap anda dapat memahami soalan dengan betul dan menyelesaikan keraguan anda!

---

Soalan yang saya jawab: Python-QA

Answer 2

Anda mungkin salah faham maksud soalan

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

Gesaan ini bermaksud len(nums1) >= m + n, khususnya anda perlu menggabungkan m item pertama nums1 dan n item terakhir nums2 ke dalam tatasusunan (senarai) baharu dan mengisihnya (bilangan elemen nums1 Tidak kurang daripada m + n)

Jadi penyelesaian anda memang salah

PS: Saya tidak tahu sama ada bahasa Inggeris saya yang lemah atau orang asing yang pada asalnya bertanya soalan ini agak tidak jelas Tujuan jawapan standard adalah untuk menggabungkan m item pertama satu senarai dan n item terakhir senarai lain ke dalam senarai baharu Dan susun, tetapi maksud soalan itu adalah untuk menggabungkan dua senarai, 囧