Sort Colors

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

Edsger Dijkstra lo planteó así: organiza objetos de tres colores en una fila, los colores rojo, blanco y azul de la bandera neerlandesa, de modo que cada color quede agrupado, en una sola pasada usando solo intercambios. Sort Colors es el mismo problema con 0, 1 y 2, y su solución es la partición de tres punteros.

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

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

Q: ¿Es la ordenación 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. Prepárate para que después te pidan una sola pasada. El conteo es una mejor herramienta cuando hay muchos colores, ya que la partición solo se divide en tres grupos.

MedioDos punteros Ordenación

+10

Recibes un arreglo nums en el que cada valor es 0, 1 o 2: tres colores, como rojo, blanco y azul. Reordena el arreglo 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 ordenación de una biblioteca.

Función

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

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

Restricciones

1 ≤ nums.length ≤ 1.5 × 10⁴
Cada nums[i] es 0, 1 o 2.
Puede faltar un color y el array 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 array contiene dos 0, tres 1 y dos 2, así que el resultado es exactamente eso: dos 0, después tres 1 y después dos 2.

Para ir más allá

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

Pistas

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

0 de 3 abiertas

Solución

Solo pueden aparecer 0, 1 y 2, así que puedes contarlos y reescribir el array en dos pasadas. Tres punteros que marcan dónde terminan los 0 y dónde empiezan los 2 lo hacen en una pasada, colocando cada valor en su sitio a medida que lo lees. Esa partición es el algoritmo de la bandera nacional neerlandesa.

Ordenamiento de burbuja a mano

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

Intuición

Sin una función de ordenación de una biblioteca, la alternativa básica es una ordenación que escribes tú. La ordenación de burbuja recorre el arreglo e intercambia los elementos vecinos que están desordenados. Cada pasada lleva al final el valor más grande que encuentra, así que después de n-1 pasadas todas las posiciones son definitivas.

Realiza aproximadamente n²/2 comparaciones: más de 10^8 para n = 1.5 × 10^4, y ninguna aprovecha que solo existen tres valores.

Algoritmo

Realiza 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 esté en su posición final, 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 finales, así que la siguiente pasada se detiene antes de 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 después vuelve a escribir

Intuición

Los valores iguales son intercambiables, así que solo importan las cantidades. En el primer ejemplo, dos 0, tres 1 y dos 2 determinan la respuesta antes de que muevas nada.

Recorre el array una vez para contar cada valor y, después, sobrescríbelo desde el principio: count[0] ceros, count[1] unos, count[2] doses. Esto es ordenamiento por conteo. Dos pasadas y tres contadores dan un tiempo O(n) y un espacio O(1).

Algoritmo

Crea tres contadores, todos en 0.
Lee cada valor y suma uno a su contador.
Escribe count[0] ceros desde el inicio, 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. 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] no se ha leído.

Lee nums[mid]. Un 1 ya está en su región, así que avanza mid. Un 0 se intercambia con nums[low] y ambos avanzan: 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 está en su lugar. Un 2 se intercambia con nums[high] y high retrocede, pero mid se queda donde está, porque el valor que viene de high no se ha leído.

Cada paso avanza mid o hace retroceder high, así que el bucle termina después de n pasos. En [2, 0, 2], el primer 2 se intercambia con el último y high baja a 1; el índice 0 todavía contiene un 2, que se intercambia con el 0; el 0 entonces se queda, dando como resultado [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

Avanzar mid 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].
Repetir el bucle mientras mid < high. Cuando ambos se encuentran, 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 caiga por debajo de cero con un índice sin signo. Un array que solo contiene doses, como [2], hace que high llegue a -1, lo que provoca un desbordamiento en un usize de Rust. En su lugar, mantén high una posición más allá de la parte que no se ha leído.

Preguntas frecuentes3

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

Edsger Dijkstra lo planteó así: organiza objetos de tres colores en una fila, los colores rojo, blanco y azul de la bandera neerlandesa, de modo que cada color quede agrupado, en una sola pasada usando solo intercambios. Sort Colors es el mismo problema con 0, 1 y 2, y su solución es la partición de tres punteros.

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

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

¿Es la ordenación 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. Prepárate para que después te pidan una sola pasada. El conteo es una mejor herramienta cuando hay muchos colores, ya que la partición solo se divide en tres grupos.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

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

Sort Colors

Función

Restricciones

Ejemplos

Pistas

Solución

Ordenamiento de burbuja a mano

Cuenta cada color y después vuelve a escribir

Una pasada con tres punteros (bandera nacional neerlandesa)

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares