python - 88. Merge Sorted Array

Answer 1

Je n'ai pas réellement posé cette question. J'ai deviné ce qu'il voulait dire et j'ai écrit le morceau de code suivant. Vous devriez comprendre le problème après l'avoir lu :

Test simple

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

Résultat :

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

Description

Cette question n'est pas si appropriée pour Python (de nombreuses questions sur la structure des données dans leetcode ont ce problème). La question d'origine parle de tableaux, mais ce dont nous parlons ici, ce sont des listes, bien que les listes de Python ressemblent davantage à des tableaux. il y a encore quelques différences.

Comme le montre le titre, la longueur de nums1 commence à partir de m+n Cela peut être dû à des raisons peu claires. m représente le nombre d'éléments m+n La description ci-dessus est la longueur de. nums1 (espace), donc dans mon exemple, j'ai utilisé 0 pour représenter un nombre dénué de sens mais pour souligner l'existence de l'espace.

fusionner1

Donc la première méthode, nums1[m:] = nums2[:n] consiste à remplir les n premiers éléments (éléments valides) de nums2 dans la seconde moitié de l'espace de nums1 (en commençant par la m+1ème position), et enfin Triez-les pour que la réponse finale soit celle que nous voulons.

fusion2

La deuxième méthode ressemble à la première méthode à première vue, mais en termes de données d'entrée qui peuvent être utilisées dans cette question, elle est en fait différente. Elle n'utilisera pas l'espace restant après nums1, mais. utilisera ajoute un nouvel espace (en utilisant nums2), ce qui entraîne une modification de la longueur (espace) de append. nums1

fusion3

Le problème avec cette approche est le même que la deuxième approche, mais plus sérieusement,

générera un nouvel objet, car ce changement n'est pas en place bien qu'il soit toujours attribué à nums1 + nums2 au final. , Cette variable ne fait plus référence à l'original nums1, et l'original nums1 n'est pas du tout affecté. nums1

J'espère que vous pourrez comprendre correctement la question et résoudre vos doutes !

---

Questions auxquelles j'ai répondu : Python-QA

Answer 2

Vous avez peut-être mal compris le sens de la question

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

Cette invite signifie len(nums1) >= m + n, plus précisément, vous devez fusionner les m premiers éléments de nums1 et les n derniers éléments de nums2 dans un nouveau tableau (liste) et le trier (le nombre d'éléments de nums1 pas moins de m + n)

Donc votre solution est effectivement fausse

PS : je ne sais pas si c'est mon mauvais anglais ou si l'étranger qui a posé cette question à l'origine est un peu flou. L'intention de la réponse standard est de fusionner les m premiers éléments d'une liste et les n derniers éléments d'une liste. une autre liste dans une nouvelle liste. Et trier, mais le sens de la question est évidemment de fusionner deux listes, 囧