Next Permutation

Q: Qual é a complexidade de tempo da próxima permutação?

O(n) . Uma varredura da direita encontra o pivô, uma segunda encontra o valor com o qual trocá-lo, e uma inversão corrige o sufixo. A memória extra é O(1) , já que tudo acontece dentro do array.

MédioArrays e strings Dois ponteiros

+10

Você recebe um array de inteiros nums, e os valores podem se repetir. Imagine todos os arranjos distintos desses valores, ordenados em ordem lexicográfica: compare dois arranjos no primeiro índice em que diferem, e aquele que tiver o menor valor nessa posição vem primeiro. Retorne o arranjo que vem logo depois de nums nessa ordem.

Se nums já for o maior arranjo, não há nenhum depois dele: retorne o menor, que corresponde aos valores ordenados em ordem crescente. Busque um tempo O(n) e memória extra O(1).

Função

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

numsinteger-array: a disposição atual dos valores
Retornainteger-array: o próximo arranjo em ordem lexicográfica ou os valores classificados em ordem crescente se nums for o maior

Restrições

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Exemplos

Entrada: nums = [2, 5, 4, 1]
Saída: [4, 1, 2, 5]
Explicação: A cauda 5, 4, 1 está diminuindo, então o 2 à sua frente precisa aumentar. O menor valor da cauda acima de 2 é 4; coloque-o ali e deixe o restante em ordem crescente: [4, 1, 2, 5].

Entrada: nums = [3, 2, 2, 1]
Saída: [1, 2, 2, 3]
Explicação: O array inteiro está em ordem decrescente, então ele é o maior arranjo de 3, 2, 2 e 1. A resposta dá a volta até o menor, [1, 2, 2, 3].

Entrada: nums = [1, 5, 1]
Saída: [5, 1, 1]
Explicação: O primeiro 1 precisa aumentar. O último 1 é igual a ele, não maior, então o único valor que pode ocupar seu lugar é 5, o que resulta em [5, 1, 1].

Para ir além

Como você encontraria, em vez disso, o arranjo anterior, aquele que vem imediatamente antes de nums em ordem lexicográfica?

Solução

Um sufixo decrescente já é tão grande quanto seus valores permitem, então a próxima disposição altera o valor imediatamente anterior a ele, o pivô. Aumente o pivô pela menor quantidade possível e, em seguida, torne o sufixo o menor possível. Isso exige duas varreduras da direita para a esquerda e uma inversão dentro do array.

Organize as listas em ordem

Correta, mas não termina nos maiores testes

Intuição

Construa as permutações em profundidade a partir dos valores ordenados, sempre tentando primeiro o menor valor ainda não usado. Isso as produz em ordem lexicográfica, então a primeira estritamente maior que nums é a resposta; se não houver nenhuma, retorne os valores ordenados. Valores repetidos geram algumas permutações duas vezes, como em 115, 151, 115, 151, 511, 511 para [1, 1, 5], mas uma cópia apenas repete uma permutação já construída, então a primeira maior ainda é a seguinte.

A quantidade cresce como n!: 12 valores distintos têm 479,001,600 permutações.

Algoritmo

Ordene uma cópia de nums em pool.
Construa as combinações em profundidade, escolhendo entradas não utilizadas de pool da esquerda para a direita.
Quando uma combinação estiver completa, compare-a com nums posição por posição.
Retorne a primeira combinação que seja maior que nums.
Se nenhuma for maior, retorne pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Encontre o pivô, troque, inverta o sufixo

Intuição

O pivô é o primeiro valor, da direita para a esquerda, que é menor que seu vizinho à direita: o 2 em [2, 5, 4, 1]. É a posição mais à direita que pode crescer, e aumentar a posição mais à direita possível mantém o aumento mínimo.

Troque o pivô pelo menor valor do sufixo que seja estritamente maior. O sufixo está em ordem decrescente, então esse é o valor maior que o pivô mais à direita: 4, resultando em [4, 5, 2, 1]. O sufixo continua em ordem decrescente, porque o pivô antigo se encaixa na posição que 4 ocupava. Como o primeiro valor agora é maior, o sufixo deve ser o menor possível, em ordem crescente, e inverter uma sequência decrescente faz isso: [4, 1, 2, 5].

Sem pivô, o array está na maior ordenação, e inverter tudo resulta na menor. Cada etapa é uma varredura ou uma inversão: tempo O(n) e memória O(1), embora a versão em R retorne uma cópia O(n).

Algoritmo

Defina i como n-2 e mova-o para a esquerda enquanto nums[i] ≥ nums[i + 1].
Se i ≥ 0, defina j como n-1 e mova-o para a esquerda enquanto nums[j] ≤ nums[i]; em seguida, troque nums[i] e nums[j].
Inverta a parte de i + 1 até o fim, usando dois índices que avançam um em direção ao outro.
Retorne nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Armadilhas e casos extremos

Usar > em vez de ≥ na busca pelo pivô. Em [3, 2, 2, 1], o par 2, 2 não é uma subida, e parar nesse ponto escolhe um pivô que não pode crescer.
Trocar por um valor igual ao pivô. Em [1, 5, 1], trocar os dois 1s não muda nada; procure um valor estritamente maior.
Trocar pelo maior valor do sufixo. Em [2, 5, 4, 1], isso coloca 5 na frente e pula todas as permutações que começam com 4.
Ignorar o caso sem pivô. A maior permutação deve voltar ordenada, invertendo todo o array.
Em Rust, um índice usize que começa em n-2 entra em pânico quando n = 1, e avançar para a esquerda além de 0 entra em pânico quando não há pivô. Use um índice com sinal ou conte a partir de 1.

Perguntas frequentes3

Qual é a complexidade de tempo da próxima permutação?

O(n). Uma varredura da direita encontra o pivô, uma segunda encontra o valor com o qual trocá-lo, e uma inversão corrige o sufixo. A memória extra é O(1), já que tudo acontece dentro do array.

Por que você inverte o sufixo em vez de ordená-lo?

Após a troca, o sufixo ainda está em ordem decrescente, então invertê-lo já o ordena em ordem crescente. Uma inversão leva O(n); uma ordenação produz o mesmo resultado em O(n log n).

O Next Permutation funciona com valores duplicados?

Sim, desde que ambas as comparações tratem valores iguais como não maiores. A busca pelo pivô ignora vizinhos iguais com ≥, e a busca pela troca ignora valores iguais ao pivô com ≤. Então, [1, 5, 1] se torna [5, 1, 1], a próxima disposição distinta.

def nextPermutation(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

nums = [2, 5, 4, 1]

Saída Esperada

[4, 1, 2, 5]