LeetCode – Fusionar matriz ordenada (Java)

Dados dos arreglos de enteros ordenados A y B, combine B en A como un arreglo ordenado.

Nota:
Puede suponer que A tiene suficiente espacio para contener elementos adicionales de B. El número de elementos inicializados en A y B son myn respectivamente.

Análisis

La clave para resolver este problema es mover los elementos de A y B hacia atrás. Si a B le quedan algunos elementos después de que A haya terminado, también debe manejar ese caso.

El mensaje para llevar de este problema es que la condición del bucle. Este tipo de condición también se utiliza para fusionar dos listas enlazadas ordenadas.

Solución Java 1

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
 
        while(m > 0 && n > 0){
            if(A[m-1] > B[n-1]){
                A[m+n-1] = A[m-1];
                m--;
            }else{
                A[m+n-1] = B[n-1];
                n--;
            }
        }
 
        while(n > 0){
            A[m+n-1] = B[n-1];
            n--;
        }
    }
}

Solución Java 2

La condición de bucle también puede usar m + n como se muestra a continuación.

public void merge(int A[], int m, int B[], int n) {
	int i = m - 1;
	int j = n - 1;
	int k = m + n - 1;
 
	while (k >= 0) {
		if (j < 0 || (i >= 0 && A[i] > B[j]))
			A[k--] = A[i--];
		else
			A[k--] = B[j--];
	}
}