Chocolate Distribution Problem

Q: Qual é a complexidade de tempo do problema da distribuição de chocolates?

A ordenação leva O(n log n) e o deslizamento da janela de m pacotes leva O(n) , então o total é O(n log n) . O espaço extra é O(n) para uma cópia ordenada, ou O(1) além da própria ordenação, se você ordenar a entrada no próprio lugar.

Q: A distribuição de chocolate é um problema de janela deslizante?

Sim, uma janela de tamanho fixo sobre os pacotes ordenados. Diferentemente de uma janela de soma acumulada, não há nada para atualizar conforme ela se move: a diferença de cada janela é uma subtração do primeiro pacote do último.

Q: É possível resolver o problema da distribuição de chocolates sem ordenar?

Os tamanhos aqui são no máximo 10^5 , então uma ordenação por contagem os ordena em O(n + 10^5) tempo, e a mesma demonstração se aplica. Com tamanhos sem limite, apenas comparações não podem superar O(n log n) : com m = 2 , a resposta é 0 exatamente quando dois pacotes são iguais, e detectar uma duplicata exige esse número de comparações no pior caso.

FácilOrdenação Janela deslizante

+10

Você tem alguns pacotes de chocolate, e packets[i] é o número de chocolates no pacote i. Cada um dos m estudantes recebe exatamente um pacote, então m pacotes diferentes são distribuídos. Escolha-os de modo que a diferença entre o maior e o menor pacote distribuído seja a menor possível.

Escreva uma função chamada minDifference que retorne essa menor diferença possível.

Função

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

packetsinteger-array: o número de chocolates em cada pacote
minteger: o número de alunos, cada um recebendo um pacote
Retornainteger: a menor diferença possível entre o maior e o menor pacote distribuído

Restrições

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Dois pacotes podem conter a mesma quantidade de chocolates.

Exemplos

Entrada: packets = [9, 3, 15, 7, 11, 4]m = 3
Saída: 4
Explicação: Em ordem crescente, os pacotes são 3, 4, 7, 9, 11 e 15. Tanto 3, 4, 7 quanto 7, 9, 11 apresentam uma diferença de 4, e nenhum grupo de três pacotes está mais próximo.

Entrada: packets = [8, 1, 5]m = 3
Saída: 7
Explicação: Há três estudantes e três pacotes, então todos os pacotes são distribuídos e a diferença é 8 - 1 = 7.

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Tentar todos os grupos de m pacotes é lento demais. A melhor escolha sempre consiste em m pacotes que ficam lado a lado depois que os pacotes são ordenados. Portanto, ordene uma vez, e a resposta é a menor diferença em qualquer janela de m pacotes vizinhos, encontrada em uma única passagem.

Conserte o menor pacote

Correta, mas não termina nos maiores testes

Intuição

Fixe o menor pacote que você vai distribuir, low. Para manter pequeno o maior pacote, pegue os m-1 menores pacotes que tenham pelo menos low. A diferença será então o m-ésimo menor pacote com pelo menos low, menos low. Tente cada pacote como low, ignore qualquer um que tenha menos de m pacotes iguais ou maiores que ele e mantenha a menor diferença.

Cada uma das n escolhas filtra e ordena até n pacotes: O(n² log n). Com n = 10^4 tamanhos diferentes, só as ordenações fazem cerca de 6 × 10^8 comparações.

Algoritmo

Inicialize best com um valor que nenhuma resposta possa exceder.
Para cada pacote low, reúna todos os pacotes que contenham pelo menos low chocolates e ordene-os.
Se houver pelo menos m deles, o m-ésimo menor menos low é um candidato.
Mantenha o menor candidato em best e retorne-o.

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

Ordene e deslize uma janela de m pacotes

Intuição

Em ordem crescente, uma janela sizes[i..i+m-1] tem seu menor pacote primeiro e seu maior por último, então sua diferença é sizes[i+m-1] - sizes[i].

A melhor escolha sempre pode ser uma janela. Se uma escolha deixar de fora um pacote que está entre o menor e o maior, troque esse pacote pelo maior. O menor permanece, e o maior só pode diminuir, então a diferença nunca aumenta. Repita até que não reste nenhuma lacuna.

No primeiro exemplo, as janelas de três fornecem 4, 5, 4 e 6, então a resposta é 4. A ordenação custa O(n log n) e o deslocamento, O(n).

Algoritmo

Ordene os pacotes em ordem crescente em sizes.
Defina best como sizes[m-1] - sizes[0], a primeira janela.
Para cada início i, de 1 a n-m, compare sizes[i+m-1] - sizes[i] com best e mantenha o menor.
Retorne 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

Armadilhas e casos extremos

Encerrar a janela em i+m em vez de i+m-1, o que mede m+1 pacotes.
Parar uma janela antes. Os valores iniciais vão de 0 até n-m, inclusive. Para [1, 10, 20, 21] com m = 2, um loop com i < n-m não encontra a única diferença de 1.
Pular a ordenação. Em [9, 3, 15, 7, 11, 4], os três primeiros pacotes diferem em 12, enquanto a resposta é 4.
Medir apenas a primeira janela. Os m pacotes menores são uma opção, mas o melhor grupo pode começar em qualquer posição.
Ordenar números como texto. Em JavaScript, sort() sem um comparador coloca 100000 antes de 9.

Perguntas frequentes3

Qual é a complexidade de tempo do problema da distribuição de chocolates?

A ordenação leva O(n log n) e o deslizamento da janela de m pacotes leva O(n), então o total é O(n log n). O espaço extra é O(n) para uma cópia ordenada, ou O(1) além da própria ordenação, se você ordenar a entrada no próprio lugar.

A distribuição de chocolate é um problema de janela deslizante?

Sim, uma janela de tamanho fixo sobre os pacotes ordenados. Diferentemente de uma janela de soma acumulada, não há nada para atualizar conforme ela se move: a diferença de cada janela é uma subtração do primeiro pacote do último.

É possível resolver o problema da distribuição de chocolates sem ordenar?

Os tamanhos aqui são no máximo 10^5, então uma ordenação por contagem os ordena em O(n + 10^5) tempo, e a mesma demonstração se aplica. Com tamanhos sem limite, apenas comparações não podem superar O(n log n): com m = 2, a resposta é 0 exatamente quando dois pacotes são iguais, e detectar uma duplicata exige esse número de comparações no pior caso.

def minDifference(packets, m):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada