Sort Colors

Q: ¿Qué es el problema de la bandera nacional neerlandesa?

Edsger Dijkstra lo planteó así: dados objetos de tres colores en una fila, los colores rojo, blanco y azul de la bandera neerlandesa, agrupa cada color en una sola pasada, usando solo intercambios. Sort Colors es el mismo problema con los números 0, 1 y 2. Su solución es la partición con tres punteros: low , mid y high .

Q: ¿Cuál es la complejidad temporal y espacial de Sort Colors?

La solución de una sola pasada se ejecuta en tiempo O(n), porque cada paso reduce en una celda la parte no leída. Usa O(1) de espacio adicional: tres índices y un valor temporal para el intercambio. El ordenamiento por conteo tiene los mismos límites, pero lee el arreglo dos veces.

Q: ¿Por qué mid no se mueve después de intercambiarse con high?

El valor que vuelve de high nunca se ha leído, así que podría ser un 0, un 1 o un 2. Si se mueve mid más allá de él, quedaría un 0 o un 2 en el medio. Un intercambio con low es diferente: todo lo que hay entre low y mid es un 1, así que se conoce el valor que vuelve y mid puede avanzar.

Q: ¿Es el ordenamiento por conteo una respuesta aceptable para Sort Colors?

Cumple con los límites de tiempo O(n) y espacio O(1), y muchos entrevistadores la aceptan como primera respuesta. Espera la pregunta de seguimiento sobre cómo hacerlo en una sola pasada, que es la partición con tres punteros. El conteo es una mejor herramienta cuando hay muchos colores, ya que la partición solo divide en tres grupos.

MedioDos punteros Ordenación

+10

Recibes un array nums en el que cada valor es 0, 1 o 2. Piensa en ellos como tres colores, por ejemplo, rojo, blanco y azul. Reordena el array para que primero vayan todos los 0, después todos los 1 y luego todos los 2, y devuélvelo.

Resuélvelo sin una función de ordenamiento de una biblioteca. La idea es usar lo que sabes sobre los valores.

Función

sortColors(nums: integer-array) → integer-array

numsinteger-array: los colores, cada uno 0, 1 o 2
Devuelveinteger-array: los mismos valores con cada 0 primero, después cada 1 y después cada 2

Restricciones

1 ≤ nums.length ≤ 1.5 × 10⁴
Cada nums[i] es 0, 1 o 2.
Puede faltar un color y el arreglo puede contener un solo color.

Ejemplos

Entrada: nums = [2, 1, 0, 2, 0, 1, 1]
Salida: [0, 0, 1, 1, 1, 2, 2]
Explicación: El arreglo contiene dos 0, tres 1 y dos 2, así que el resultado es exactamente ese: dos 0, después tres 1 y después dos 2.

+17 pruebas ocultas al enviar

Para ir más allá

¿Qué cambiarías si hubiera k colores en lugar de tres, con k mucho menor que la longitud del arreglo?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cualquier ordenación produce el orden correcto, así que la verdadera pregunta es qué te permiten omitir los tres valores. Como solo pueden aparecer 0, 1 y 2, puedes contarlos y reescribir el arreglo en dos pasadas. Con tres punteros que marcan dónde terminan los 0 y dónde empiezan los 2, incluso puedes colocar cada valor en su sitio en una sola pasada. Esa partición en una pasada es el algoritmo de la bandera nacional neerlandesa.

Ordenamiento burbuja a mano

Correcto, pero no termina con las pruebas más grandes

Intuición

Una ordenación de biblioteca pasaría en O(n log n), pero las reglas del problema la descartan, porque quien entrevista quiere ver qué haces con el hecho de que solo hay tres valores. La opción básica es entonces una ordenación que escribas tú mismo, y la más sencilla de implementar correctamente es la ordenación de burbuja: recorre el array y, siempre que dos elementos vecinos estén desordenados, intercámbialos.

Una pasada lleva el valor más grande que encuentra hasta el final, como una burbuja que sube. Después de la primera pasada, la última posición queda definitiva; después de la segunda, quedan definitivas las dos últimas, así que n-1 pasadas dejan todo el array ordenado. En [2, 1, 0], la primera pasada mueve el 2 hasta el final, lo que da [1, 0, 2], y la segunda pasada intercambia el 1 y el 0.

Es lenta porque cada pasada compara todos los pares que todavía no están en su posición definitiva: aproximadamente n²/2 comparaciones en total. Con n = 1.5 × 10^4, eso supone más de 10^8 comparaciones, además de un intercambio por cada par que inicialmente está desordenado, y nada de ese trabajo aprovecha el hecho de que solo existen tres valores.

Algoritmo

Ejecuta n-1 pasadas sobre el arreglo.
En cada pasada, compara cada par de elementos vecinos nums[j] y nums[j + 1] que aún no sea definitivo e intercámbialos cuando el de la izquierda sea mayor.
Después de la pasada número done (contando desde 0), las últimas done + 1 posiciones contienen sus valores definitivos, así que la siguiente pasada se detiene antes de llegar a ellas.
Devuelve nums.

def sortColors(nums):
    n = len(nums)
    for done in range(n - 1):
        # One pass: the largest value left so far bubbles to index n-1-done.
        for j in range(n - 1 - done):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

Cuenta cada color y luego vuelve a escribirlo

Intuición

La ordenación por burbuja dedica todo su tiempo a comparar elementos vecinos, pero ya sabes qué valores existen. Si el arreglo contiene dos 0, tres 1 y dos 2, la respuesta está definida antes de mover nada: dos 0, tres 1, dos 2. Solo importan las cantidades.

Así que recorre el arreglo una vez y cuenta cada valor. Después sobrescríbelo desde el inicio: count[0] ceros, después count[1] unos, después count[2] doses. Esto es ordenación por conteo y es segura en este caso porque los valores iguales son intercambiables. Un 1 es un 1, así que no hace falta conservar nada del orden original.

Eso son dos recorridos y tres contadores, tiempo O(n) y espacio O(1). Cumple los límites y es la respuesta natural cuando hay muchos colores. La pregunta de seguimiento por la que se conoce este problema es si puedes hacerlo leyendo el arreglo una sola vez.

Algoritmo

Crea tres contadores, todos en 0.
Lee cada valor y suma uno a su contador.
Escribe count[0] ceros desde el principio, después count[1] unos y después count[2] doses.
Devuelve nums.

def sortColors(nums):
    count = [0, 0, 0]  # how many 0s, 1s and 2s
    for x in nums:
        count[x] += 1
    i = 0
    for color in range(3):
        for _ in range(count[color]):
            nums[i] = color
            i += 1
    return nums

Una pasada con tres punteros (bandera nacional neerlandesa)

Intuición

Haz crecer tres regiones mientras lees: los 0 al principio, los 1 después, los 2 al final y una parte sin leer entre los 1 y los 2. Tres índices marcan los límites. Todo lo que está antes de low es 0, todo lo que va desde low hasta antes de mid es 1, todo lo que está después de high es 2, y nums[mid] hasta nums[high] todavía no se ha leído.

Lee nums[mid]. Un 1 ya está en su región, así que avanza mid. Un 0 pertenece al principio: intercámbialo con nums[low] y avanza tanto low como mid. El valor que vuelve de low es un 1 (o el mismo 0, si todavía no se ha visto ningún 1), así que ya está en su sitio. Un 2 pertenece al final: intercámbialo con nums[high] y retrocede high, pero deja mid donde está, porque el valor que vino de high aún no se ha leído.

Cada paso avanza mid o retrocede high, así que la parte sin leer pierde una celda cada vez y el bucle termina después de n pasos. Traza [2, 0, 2]: el primer 2 se intercambia con el último 2 y high baja a 1; el índice 0 todavía contiene un 2, que se intercambia con el 0 y high baja a 0; el índice 0 ahora contiene el 0, que se queda en su sitio, y obtienes [0, 2, 2].

Algoritmo

Establece low = 0, mid = 0 y high en el último índice.
Mientras mid ≤ high, lee nums[mid].
Si es 0, intercámbialo con nums[low] y mueve low y mid un paso a la derecha.
Si es 1, mueve mid un paso a la derecha.
Si es 2, intercámbialo con nums[high] y mueve high un paso a la izquierda. Deja mid en su lugar.
Devuelve nums.

def sortColors(nums):
    # nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            # The value swapped in from high is unread, so mid stays.
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

Errores comunes y casos límite

La versión de una sola pasada es breve, y casi todos los errores que contiene se deben a un puntero que se mueve cuando no debería.

Mover mid hacia delante después de intercambiar con high. El valor que llega no se ha leído. En [1, 2, 0], el 2 se intercambia con el 0, y omitir el 0 devuelve [1, 0, 2].
Recorrer el bucle mientras mid < high cuando high es el último índice sin leer. Cuando ambos coinciden, esa celda todavía no se ha leído. En [1, 0], el bucle se detiene antes de leer el 0 y devuelve [1, 0].
Permitir que high baje de cero con un índice sin signo. Un arreglo que solo contiene 2, como [2], hace que high llegue a -1. En Rust, donde los índices son usize, mantén high una posición más allá de la parte sin leer, como hace el código de Rust.
Suponer que aparecen todos los colores. [2, 0, 2] no contiene ningún 1, y un arreglo puede contener un solo color. Las reglas de los punteros manejan ambos casos sin casos especiales, así que no añadas ninguno.

Preguntas frecuentes4

¿Qué es el problema de la bandera nacional neerlandesa?

Edsger Dijkstra lo planteó así: dados objetos de tres colores en una fila, los colores rojo, blanco y azul de la bandera neerlandesa, agrupa cada color en una sola pasada, usando solo intercambios. Sort Colors es el mismo problema con los números 0, 1 y 2. Su solución es la partición con tres punteros: low, mid y high.

¿Cuál es la complejidad temporal y espacial de Sort Colors?

La solución de una sola pasada se ejecuta en tiempo O(n), porque cada paso reduce en una celda la parte no leída. Usa O(1) de espacio adicional: tres índices y un valor temporal para el intercambio. El ordenamiento por conteo tiene los mismos límites, pero lee el arreglo dos veces.

¿Por qué mid no se mueve después de intercambiarse con high?

El valor que vuelve de high nunca se ha leído, así que podría ser un 0, un 1 o un 2. Si se mueve mid más allá de él, quedaría un 0 o un 2 en el medio. Un intercambio con low es diferente: todo lo que hay entre low y mid es un 1, así que se conoce el valor que vuelve y mid puede avanzar.

¿Es el ordenamiento por conteo una respuesta aceptable para Sort Colors?

Cumple con los límites de tiempo O(n) y espacio O(1), y muchos entrevistadores la aceptan como primera respuesta. Espera la pregunta de seguimiento sobre cómo hacerlo en una sola pasada, que es la partición con tres punteros. El conteo es una mejor herramienta cuando hay muchos colores, ya que la partición solo divide en tres grupos.

Python

def sortColors(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 1, 0, 2, 0, 1, 1]

Esperado

[0, 0, 1, 1, 1, 2, 2]

Sort Colors

Función

Restricciones

Ejemplos

Pistas

Solución

Ordenamiento burbuja a mano

Cuenta cada color y luego vuelve a escribirlo

Una pasada con tres punteros (bandera nacional neerlandesa)

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares