Dos punteros en Java

Problema

La tarjeta regalo y cada par

Un cliente tiene una tarjeta regalo y quiere gastarla hasta el último céntimo: dos productos que juntos cuesten exactamente lo que la tarjeta. El sitio los busca con dos bucles anidados, comprobando cada par:

static long checks = 0;

static int[] allPairs(int[] prices, int card) {
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            checks++;
            if (prices[i] + prices[j] == card) {
                return new int[] {i, j};
            }
        }
    }
    return null;
}

La lista de precios son 1000 productos a 2 €, 4 €, …, 2000 €, y la tarjeta es de 2001 €. La suma de dos precios pares nunca es impar, así que no hay ninguna pareja. Este es el peor caso: los bucles llegan hasta el final.

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
    prices[i] = 2 * (i + 1);
}
int card = 2 * n + 1;
int[] pair = allPairs(prices, card);
System.out.println("Pareja: " + (pair == null ? "ninguna" : "encontrada"));
System.out.println("Comprobaciones: " + checks);

Pareja: ninguna
Comprobaciones: 499500

Casi medio millón de comprobaciones para 1000 productos. Hay n(n − 1) / 2 pares, así que esto es O(n²): para 100 000 productos son unos 5000 millones.

Y la lista de precios está ordenada por precio, pero los bucles no lo aprovechan.

La idea

Uno a la izquierda, el otro a la derecha

Pon un dedo en el precio más barato y otro en el más caro. Los dedos son índices: lo y hi. Suma los dos precios:

si la suma es igual a la tarjeta, has terminado;
si es poco, el precio barato sale: ni siquiera con el precio más caro todavía en juego basta. lo avanza un precio a la derecha;
si es mucho, el precio caro sale: es demasiado incluso con el más barato. hi retrocede un precio a la izquierda.

Cada paso descarta un precio para siempre, y no se pierde ningún par que sea la respuesta. Cuando lo y hi se encuentran, los precios se han acabado. Como máximo n − 1 pasos: O(n).

Esto se llama dos punteros: dos índices que recorren el arreglo, y cada comparación dice cuál de ellos se mueve. Aquí avanzan el uno hacia el otro. Conoces la idea de la búsqueda binaria, donde lo y hi guardan el rango. Allí cada sondeo descarta la mitad, aquí descarta un precio.

La condición es la misma: el arreglo tiene que estar ordenado. Solo entonces es cierto que «más a la derecha es más caro».

Míralo

lo y hi en la lista de precios

static int[] findPair(int[] prices, int card) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo < hi) {
        int sum = prices[lo] + prices[hi];
        if (sum == card) {
            return new int[] {lo, hi};
        } else if (sum < card) {
            lo++;
        } else {
            hi--;
        }
    }
    return null;
}

int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36};
int[] pair = findPair(prices, 50);
if (pair == null) {
    System.out.println("No hay pareja para 50 €");
} else {
    System.out.println(prices[pair[0]] + " €" + " + " + prices[pair[1]] + " €");
}

19 € + 31 €

static int[] findPair(int[] prices, int card) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo < hi) {
        int sum = prices[lo] + prices[hi];
        if (sum == card) {
            return new int[] {lo, hi};
        } else if (sum < card) {
            lo++;
        } else {
            hi--;
        }
    }
    return null;
}

Paso a paso, en palabras

La lista de precios está ordenada: 10 precios. La tarjeta regalo es de 50 €. lo está en el precio más barato, hi en el más caro.
3 € + 36 € = 39 € < 50 €: es poco. Ni siquiera el precio más caro basta para 3 €, así que 3 € sale: lo avanza a la derecha.
5 € + 36 € = 41 € < 50 €: es poco. Ni siquiera el precio más caro basta para 5 €, así que 5 € sale: lo avanza a la derecha.
8 € + 36 € = 44 € < 50 €: es poco. Ni siquiera el precio más caro basta para 8 €, así que 8 € sale: lo avanza a la derecha.
12 € + 36 € = 48 € < 50 €: es poco. Ni siquiera el precio más caro basta para 12 €, así que 12 € sale: lo avanza a la derecha.
15 € + 36 € = 51 € > 50 €: es mucho. 36 € es demasiado incluso con el precio más barato, así que 36 € sale: hi retrocede a la izquierda.
15 € + 31 € = 46 € < 50 €: es poco. Ni siquiera el precio más caro basta para 15 €, así que 15 € sale: lo avanza a la derecha.
19 € + 31 € = 50 €: exactamente la tarjeta. findPair devuelve los índices 5 y 8.
7 sumas en lugar de 45 pares. Cada paso descarta un precio para siempre, así que son como máximo n − 1 pasos.

La función devuelve un arreglo con los dos índices, y null cuando no hay pareja.

Más precisamente, para curiosos

Por qué no se pierde ninguna pareja. Digamos que la respuesta es el par de índices i y j, i < j. Mientras lo ≤ i y hi ≥ j, los punteros no pueden saltarse la respuesta:

si lo < i, la suma de lo y hi es como máximo la suma de i y hi. Si es poca, lo avanza a la derecha con razón, sin pasar de i;
si hi > j, de la misma manera hi retrocede a la izquierda con razón, sin pasar de j.

Cuando lo llega a i y hi llega a j, la suma es exactamente la tarjeta. Si hay varios pares, los punteros encuentran el más externo: el del precio más barato.

Pruébalo

Predice qué pareja

La tarjeta es de 43 €. La lista de precios tiene dos pares con esa suma: 12 € + 31 € y 19 € + 24 €. ¿Qué imprime el programa?

static int[] findPair(int[] prices, int card) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo < hi) {
        int sum = prices[lo] + prices[hi];
        if (sum == card) {
            return new int[] {lo, hi};
        } else if (sum < card) {
            lo++;
        } else {
            hi--;
        }
    }
    return null;
}

int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36};
int[] pair = findPair(prices, 43);
if (pair == null) {
    System.out.println("No hay pareja para 43 €");
} else {
    System.out.println(prices[pair[0]] + " €" + " + " + prices[pair[1]] + " €");
}

Respuesta

19 € + 24 €

No hay pareja para 43 €

12 € + 31 €

Pruébalo

Completa

La suma es menor que la tarjeta. ¿Qué puntero se mueve, y en qué dirección?

static int[] findPair(int[] prices, int card) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo < hi) {
        int sum = prices[lo] + prices[hi];
        if (sum == card) {
            return new int[] {lo, hi};
        } else if (sum < card) {
            ;
        } else {
            hi--;
        }
    }
    return null;
}

Pruébalo

Encuentra el error

La tarjeta es de 50 €, y 19 € + 31 € está en la lista de precios. La función dice que no hay pareja:

int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36};
int[] pair = findPair(prices, 50);
if (pair == null) {
    System.out.println("No hay pareja para 50 €");
} else {
    System.out.println(prices[pair[0]] + " €" + " + " + prices[pair[1]] + " €");
}

No hay pareja para 50 €

Elige la línea con el error.

Míralo

Cuántos pasos

La misma lista de precios de 1000 productos y la tarjeta de 2001 €, y la función cuenta los pasos de su bucle:

static long steps = 0;

static int[] findPair(int[] prices, int card) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo < hi) {
        steps++;
        int sum = prices[lo] + prices[hi];
        if (sum == card) {
            return new int[] {lo, hi};
        } else if (sum < card) {
            lo++;
        } else {
            hi--;
        }
    }
    return null;
}

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
    prices[i] = 2 * (i + 1);
}
int card = 2 * n + 1;
int[] pair = findPair(prices, card);
System.out.println("Pareja: " + (pair == null ? "ninguna" : "encontrada"));
System.out.println("Pasos: " + steps);

Pareja: ninguna
Pasos: 999

999 pasos en lugar de 499 500 comprobaciones. Las dos funciones dan la misma respuesta, y para 100 000 productos la diferencia es 99 999 pasos frente a unos 5000 millones.

Ejecútalas en el navegador. La tercera curva es para una lista de precios sin ordenar: primero el ordenamiento por mezcla, luego los dos punteros.

Cada par O(n²)
Dos punteros (lista ordenada) O(n)
Ordenar y luego dos punteros O(n log n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Cada par	45	499.500	49.995.000	≈ 4.999.500.000
Dos punteros (lista ordenada)	9	999	9999	99.999
Ordenar y luego dos punteros	31	9692	130.424	1.636.539

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static int[] findPair(int[] prices, int card) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo < hi) {
        int sum = prices[lo] + prices[hi];
        if (sum == card) {
            return new int[] {lo, hi};
        } else if (sum < card) {
            lo++;
        } else {
            hi--;
        }
    }
    return null;
}

Por encima de 10 000 no ejecutamos cada par: esos valores van con ≈. Ordenar cuesta más que los propios punteros, pero su curva es O(n log n) y sigue muy por debajo de O(n²).

La idea

Si la lista está ordenada

Los dos punteros necesitan un arreglo ordenado. Cuando no lo está:

Ordénalo primero. Ordenar es O(n log n), los punteros O(n), en total O(n log n). Para 100 000 precios son unos 1,6 millones de operaciones frente a unos 5000 millones. Ordenar gana casi siempre.
Si buscas muchas veces en la misma lista (cada cliente con otra tarjeta), ordenas una vez, y cada búsqueda después es O(n).
Los índices cambian. Después de ordenar, prices[5] ya no es el quinto producto del catálogo. Si necesitas los productos, ordena pares (precio, producto) u objetos por precio.

int[] prices = {27, 3, 36, 15, 8, 31, 19, 5, 24, 12};
Arrays.sort(prices);
System.out.println(Arrays.toString(prices));
int[] pair = findPair(prices, 50);
if (pair == null) {
    System.out.println("No hay pareja para 50 €");
} else {
    System.out.println(prices[pair[0]] + " €" + " + " + prices[pair[1]] + " €");
}

[3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
19 € + 31 €

También hay un camino sin ordenar: recorres los precios una vez y guardas los que has visto en un conjunto. Para cada precio preguntas si card − price ya se ha visto. Eso es O(n) en promedio, con una tabla hash y n de memoria adicional. Los dos punteros no usan memoria adicional, pero necesitan un arreglo ordenado.

Míralo

La misma idea: mezclar y duplicados

Los dos punteros no siempre avanzan el uno hacia el otro. A veces avanzan en la misma dirección.

Mezclar dos listas ordenadas. Los pedidos del sitio web y los del teléfono se numeran con un solo contador pero se guardan por separado, cada lista ordenada. El informe diario quiere una lista ordenada. i recorre la primera, j la segunda, y cada vez el número menor pasa al resultado. Esta es la mezcla del ordenamiento por mezcla:

static int[] merge(int[] a, int[] b) {
    int[] out = new int[a.length + b.length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) {
            out[k++] = a[i++];
        } else {
            out[k++] = b[j++];
        }
    }
    while (i < a.length) {
        out[k++] = a[i++];
    }
    while (j < b.length) {
        out[k++] = b[j++];
    }
    return out;
}

int[] web = {1003, 1007, 1012, 1020};
int[] phone = {1001, 1009, 1010, 1031, 1044};
System.out.println(Arrays.toString(merge(web, phone)));

[1001, 1003, 1007, 1009, 1010, 1012, 1020, 1031, 1044]

Duplicados en el sitio. Los precios de una importación están ordenados, pero con duplicados, y el filtro tiene que mostrar cada precio una vez. read lee cada precio, y write es el lugar para el siguiente nuevo. Todo lo que hay antes de write está terminado y libre de duplicados:

static int unique(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    int write = 1;
    for (int read = 1; read < prices.length; read++) {
        if (prices[read] != prices[write - 1]) {
            prices[write] = prices[read];
            write++;
        }
    }
    return write;
}

int[] prices = {5, 5, 8, 12, 12, 12, 19, 24, 24};
int k = unique(prices);
System.out.println("Precios distintos: " + k);
System.out.println(Arrays.toString(Arrays.copyOf(prices, k)));

Precios distintos: 5
[5, 8, 12, 19, 24]

Un arreglo en Java tiene una longitud fija: la función devuelve cuántos precios distintos hay, y el programa muestra solo esos (Arrays.copyOf(prices, k)).

Ambos son O(n): cada puntero recorre la lista una vez.

Míralo

Un código promocional espejo

La campaña «Código espejo» acepta solo códigos promocionales que se leen igual desde los dos extremos. Los punteros empiezan en los dos extremos y comparan carácter por carácter hasta encontrarse:

static boolean isMirror(String code) {
    int lo = 0;
    int hi = code.length() - 1;
    while (lo < hi) {
        if (code.charAt(lo) != code.charAt(hi)) {
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

System.out.println(isMirror("AB7CC7BA"));
System.out.println(isMirror("AB7CD7BA"));

true
false

Más precisamente, para curiosos

La misma comprobación se puede escribir en una línea, comparando el código con una copia invertida:

String code = "AB7CC7BA";
System.out.println(code.equals(new StringBuilder(code).reverse().toString()));

true

new StringBuilder(code).reverse() crea una cadena nueva de la misma longitud.

La respuesta es la misma y sigue siendo O(n). La diferencia: la copia son n caracteres más de memoria y siempre se hace entera, mientras que los punteros se detienen en la primera diferencia. Para un código promocional de 8 caracteres no importa. Para comprobar millones de líneas de un registro, sí.

Los mismos punteros dan la vuelta a un arreglo en el sitio: intercambia lo y hi, y muévelos hacia dentro.

Ejercicio

El más cercano a la tarjeta

Resuelve la tarea en tu editor.

El más cercano a la tarjeta. No siempre hay un par exacto. Entonces la tienda ofrece los dos productos que juntos más se acercan a la tarjeta sin pasarse. La lista de precios es 3 €, 5 €, 8 €, 12 €, 15 €, 19 €, 24 €, 27 €, 31 € y 36 €, y la tarjeta es de 45 €. Con dos punteros: si la suma está dentro de la tarjeta, recuérdala si es mejor que la mejor hasta ahora, y mueve lo. Si no, mueve hi.

Más cercano a 45 €: 8 € + 36 € = 44 €

Más tareas

Un código espejo con guiones. Los códigos promocionales se imprimen con guiones: AB7-CC-7BA. Salta los guiones: cada puntero los salta antes de comparar.
Dos por viaje. Los paquetes están ordenados por peso, y un viaje del mensajero lleva como máximo dos paquetes de hasta 30 kg en total. ¿Cuántos viajes hacen falta como mínimo? Junta el más ligero con el más pesado si caben; si no, el más pesado va solo.
Productos comunes. Dos listas ordenadas de números de producto: la del almacén y la del pedido. Encuentra con dos punteros en la misma dirección qué números están en las dos.

Test

Ponte a prueba

1. La lista de precios está ordenada. lo está en 8 €, hi en 36 €, la tarjeta es de 50 €. La suma es 44 €. ¿Qué haces?hi retrocede a la izquierdaVuelves al principiolo avanza a la derecha: 8 € no bastan ni con el precio más caro

2. La lista de precios tiene 100 000 productos, y no hay ninguna pareja para la tarjeta. ¿Cuántas sumas calculan los dos punteros?Unas 17, tantas como la búsqueda binaria99 999Unos 5000 millones

3. La lista de precios no está ordenada. ¿Cuál de las tres es la más rápida?Ordenarla (O(n log n)) y ejecutar los dos punteros (O(n))Cada par (O(n²)), porque ordenar cuesta demasiadoEjecutar los dos punteros directamente sobre la lista sin ordenar

4. Quitas los duplicados de la lista ordenada en el sitio, con read y write. ¿Qué es verdad?read y write avanzan el uno hacia el otro desde los dos extremosNecesitas una lista nueva de la misma longitudread recorre cada elemento, y write muestra dónde termina la parte terminada

5. ¿Por qué comprobar un código promocional espejo con dos punteros es mejor que compararlo con una copia invertida?La copia invertida da una respuesta incorrectaEs O(log n)No hace ninguna copia y se detiene en la primera diferencia

Dos punteros

Cookies