casse-tête en utilisant des tableaux

Question

Ma première matrice M + taille N et deuxième tableau de taille N.

disons m = 4, n = 5
un [] = 1,3,5,7,0, 0,0,0,0

b [] = 2,4,6,8,10

maintenant, comment puis-je fusionner ces deux tableaux sans utiliser des algorithmes de tri externes et tout autre tableau temporaire (fusion inplace) mais la complexité doit être o (n). Le tableau de résultat doit être trié.

Answer 1

fourni un est exactement la bonne taille et les tableaux sont déjà triés (comme cela semble être le cas), le pseudo-code suivant devrait aider:

# 0 1 2 3 4 5 6 7 8 
a = [1,3,5,7,0,0,0,0,0] 
b = [2,4,6,8,10] 
afrom = 3 
bfrom = 4 

ato = 8 
while bfrom >= 0: 
    if afrom == -1: 
     a[ato] = b[bfrom] 
     ato = ato - 1 
     bfrom = bfrom - 1 
    else: 
     if b[bfrom] > a[afrom]: 
      a[ato] = b[bfrom] 
      ato = ato - 1 
      bfrom = bfrom - 1 
     else: 
      a[ato] = a[afrom] 
      ato = ato - 1 
      afrom = afrom - 1 
print a 

C'est fondamentalement une fusion des deux listes en une, commençant aux extrémités. Une fois que bfrom a atteint -1, il n'y a plus d'éléments dans b, donc le reste dans a était inférieur au plus bas dans b. Par conséquent, le reste de a peut rester inchangé.

Si a tourne en premier, il est question de transférer le reste de b puisque tous les éléments a ont été transférés au-dessus ato déjà.

Ceci est O (n) tel que demandé et entraînerait quelque chose comme:

[1, 2, 3, 4, 5, 6, 7, 8, 10] 

---

Comprendre que pseudo-code et le traduire dans votre langue spécifique est un travail pour vous, maintenant que vous 'ai déclaré ses devoirs :-)

Answer 2

for (i = 0; i < N; i++) { 
    a[m+i] = b[i]; 
} 

Ceci effectuera une fusion sur place (concaténation).

Si vous demandez une fusion ordonnée, cela n'est pas possible dans O (N). Si c'était possible, vous pourriez l'utiliser pour trier en O (N). Et bien sûr O (N log N) est l'algorithme de tri de cas généraux le plus connu ...

Je dois vous poser, cependant, en regardant vos dernières questions: vous nous demandez simplement de l'aide pour vos devoirs? Vous savez que c'est correct de dire "c'est devoirs", et personne ne se moquera de vous, non? Nous ferons même de notre mieux pour vous aider à apprendre.

Answer 3

Voulez-vous un tableau trié? Sinon cela devrait faire

for(int i=a.length-1,j=0;i >=0; i--) { a[i] = b[j++]; }

Answer 4

Vous pouvez jeter un oeil à in-place counting sort qui fonctionne tant que vous connaissez la plage d'entrée. Effectivement O (n).