Chocolate Distribution Problem

Q: ¿Cuál es la complejidad temporal del problema de distribución de chocolates?

La ordenación tarda O(n log n) y deslizar la ventana de m paquetes tarda O(n) , así que el total es O(n log n) . El espacio adicional es O(n) para una copia ordenada, o O(1) además de la propia ordenación si ordenas la entrada in situ.

Q: ¿Es el problema de distribución de chocolate un problema de ventana deslizante?

Sí, una ventana de tamaño fijo sobre los paquetes ordenados. A diferencia de una ventana de suma acumulada, no hay nada que actualizar a medida que se desplaza: la diferencia de cada ventana se obtiene restando su primer paquete al último.

Q: ¿Se puede resolver el problema de la distribución de chocolate sin ordenar?

Los tamaños aquí son como máximo 10^5 , así que un ordenamiento por conteo los ordena en tiempo O(n + 10^5) y se aplica la misma diapositiva. Con tamaños sin límite, las comparaciones por sí solas no pueden superar O(n log n) : con m = 2 , la respuesta es 0 exactamente cuando dos paquetes son iguales, y detectar un duplicado requiere esa cantidad de comparaciones en el peor caso.

FácilOrdenación Ventana deslizante

+10

Tienes algunos paquetes de chocolate, y packets[i] es la cantidad de chocolates que hay en el paquete i. Cada uno de los m estudiantes recibe exactamente un paquete, así que se entregan m paquetes diferentes. Elígelos de modo que la diferencia entre el paquete más grande y el más pequeño entregados sea lo más pequeña posible.

Escribe una función llamada minDifference que devuelva esa diferencia mínima posible.

Función

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: la cantidad de chocolates en cada paquete
minteger: el número de estudiantes, cada uno recibe un paquete
Devuelveinteger: la menor diferencia posible entre el paquete más grande y el más pequeño repartidos

Restricciones

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Dos paquetes pueden contener la misma cantidad de chocolates.

Ejemplos

Entrada: packets = [9, 3, 15, 7, 11, 4]m = 3
Salida: 4
Explicación: Ordenados, los paquetes son 3, 4, 7, 9, 11 y 15. Tanto 3, 4, 7 como 7, 9, 11 dan una diferencia de 4, y no hay tres paquetes más cercanos entre sí.

Entrada: packets = [8, 1, 5]m = 3
Salida: 7
Explicación: Hay tres estudiantes y tres paquetes, así que se envía cada paquete y la diferencia es 8 - 1 = 7.

Pistas

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

0 de 3 abiertas

Solución

Probar cada grupo de m paquetes es demasiado lento. La mejor selección siempre consiste en m paquetes que quedan uno junto a otro una vez ordenados. Así que ordénalos una vez y la respuesta será la menor diferencia entre cualquier ventana de m paquetes vecinos, encontrada en una sola pasada.

Corrige el paquete más pequeño

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

Intuición

Fija el paquete más pequeño que entregas, low. Para mantener pequeño el más grande, toma los m-1 paquetes más pequeños que tengan al menos low. La diferencia es entonces el paquete número m más pequeño que tenga al menos low, menos low. Prueba cada paquete como low, omite cualquiera que tenga menos de m paquetes iguales o superiores a él y conserva la diferencia más pequeña.

Cada una de las n opciones filtra y ordena hasta n paquetes: O(n² log n). Con n = 10^4 tamaños distintos, solo las ordenaciones realizan alrededor de 6 × 10^8 comparaciones.

Algoritmo

Inicia best con un valor que ninguna respuesta pueda superar.
Para cada paquete low, reúne todos los paquetes que tengan al menos low chocolates y ordénalos.
Si hay al menos m de ellos, el m-ésimo más pequeño menos low es un candidato.
Conserva el candidato más pequeño en best y devuélvelo.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Ordena y desliza una ventana de m paquetes

Intuición

En orden ascendente, una ventana sizes[i..i+m-1] tiene primero el paquete más pequeño y al final el más grande, así que su diferencia es sizes[i+m-1] - sizes[i].

La mejor elección siempre puede ser una ventana. Si una elección omite un paquete que está entre el más pequeño y el más grande, intercambia ese paquete por el más grande. El más pequeño se mantiene y el más grande solo puede reducirse, así que la diferencia nunca aumenta. Repite hasta que no quede ningún hueco.

En el primer ejemplo, las ventanas de tres dan 4, 5, 4 y 6, así que la respuesta es 4. La ordenación cuesta O(n log n) y el desplazamiento O(n).

Algoritmo

Ordena los paquetes en orden creciente en sizes.
Establece best en sizes[m-1] - sizes[0], la primera ventana.
Para cada inicio i desde 1 hasta n-m, compara sizes[i+m-1] - sizes[i] con best y conserva el menor.
Devuelve best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Errores comunes y casos límite

Terminar la ventana en i+m en lugar de i+m-1, lo que mide m+1 paquetes.
Detenerse una ventana antes. Los inicios van de 0 a n-m, inclusive. Para [1, 10, 20, 21] con m = 2, un bucle con i < n-m no detecta la única diferencia de 1.
Omitir la ordenación. En [9, 3, 15, 7, 11, 4], los primeros tres paquetes difieren en 12, mientras que la respuesta es 4.
Medir solo la primera ventana. Los m paquetes más pequeños son una opción, pero el mejor grupo puede empezar en cualquier lugar.
Ordenar los números como texto. En JavaScript, sort() sin comparador coloca 100000 antes de 9.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del problema de distribución de chocolates?

La ordenación tarda O(n log n) y deslizar la ventana de m paquetes tarda O(n), así que el total es O(n log n). El espacio adicional es O(n) para una copia ordenada, o O(1) además de la propia ordenación si ordenas la entrada in situ.

¿Es el problema de distribución de chocolate un problema de ventana deslizante?

Sí, una ventana de tamaño fijo sobre los paquetes ordenados. A diferencia de una ventana de suma acumulada, no hay nada que actualizar a medida que se desplaza: la diferencia de cada ventana se obtiene restando su primer paquete al último.

¿Se puede resolver el problema de la distribución de chocolate sin ordenar?

Los tamaños aquí son como máximo 10^5, así que un ordenamiento por conteo los ordena en tiempo O(n + 10^5) y se aplica la misma diapositiva. Con tamaños sin límite, las comparaciones por sí solas no pueden superar O(n log n): con m = 2, la respuesta es 0 exactamente cuando dos paquetes son iguales, y detectar un duplicado requiere esa cantidad de comparaciones en el peor caso.

def minDifference(packets, m):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

packets = [9, 3, 15, 7, 11, 4]
m = 3

Salida Esperada