Rotate Array

Q: O que acontece quando k é maior que o comprimento do array?

A cada n passos, o array volta à sua ordem inicial, então somente k mod n passos importam. Rotacionar [10, 20, 30] em 7 posições é o mesmo que rotacioná-lo em 1 posição, o que resulta em [30, 10, 20] . Quando k é múltiplo de n , o array não muda.

Q: Como girar um array para a esquerda?

Uma rotação para a esquerda por k é uma rotação para a direita por n - (k mod n) . Com reversões, inverta os primeiros k mod n valores, depois o restante e, por fim, o array inteiro. Ambos mantêm o tempo O(n).

MédioArrays e strings Dois ponteiros

+10

Você recebe um array de números inteiros nums e um número k. Gire o array para a direita em k passos: em cada passo, todos os valores se movem uma posição para a direita, e o último valor retorna ao início. Retorne o array girado.

k pode ser muito maior que o comprimento do array.

Função

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: o array de números inteiros a ser rotacionado
kinteger: quantos passos girar para a direita
Retornainteger-array: nums rotacionado para a direita em k passos

Restrições

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Exemplos

Entrada: nums = [4, 9, 1, 6, 3]k = 2
Saída: [6, 3, 4, 9, 1]
Explicação: Dois passos para a direita levam os dois últimos valores, 6 e 3, para o início. Os outros três valores se movem duas posições para a direita e mantêm a ordem: [6, 3, 4, 9, 1].

Para ir além

Você consegue fazer uma rotação no próprio lugar, movendo cada valor diretamente para (i + k) mod n e levando adiante o valor que ele desloca? Quantos ciclos isso forma?

Dicas

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

0 de 3 abertas

Solução

A cada n passos, o array volta ao ponto inicial, então primeiro reduza k, que pode ser 10^9, para k mod n. Em seguida, escreva cada valor diretamente em seu índice final em um segundo array ou obtenha o mesmo resultado dentro do array com três inversões e memória extra O(1).

Copie cada valor para seu novo índice

Intuição

Após k etapas, o valor no índice i fica em (i + k) mod n, então escreva-o diretamente nessa posição sem executar as etapas. Primeiro, reduza k para k mod n: uma rotação de n coloca todos os valores de volta onde estavam, então, com k = 7 e n = 3, resta apenas uma etapa.

Uma única passagem posiciona todos os n valores: tempo O(n), mais memória O(n) para o resultado. Não é possível escrever diretamente em nums dessa forma, pois cada escrita sobrescreveria um valor que você ainda não moveu.

Algoritmo

Defina n como o comprimento de nums e substitua k por k mod n.
Crie um array de resultado com comprimento n.
Para cada índice i, armazene nums[i] em result[(i + k) mod n].
Retorne o resultado.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Três inversões no próprio lugar

Intuição

Divida o array em A, os primeiros n-k valores, e B, os últimos k. O array rotacionado é B seguido de A, cada bloco na ordem original. Inverter o array inteiro altera tanto a ordem dos blocos quanto a ordem dentro de cada um, então B vem primeiro, mas fica invertido, e o mesmo acontece com A. Inverter cada bloco novamente restaura a ordem interna.

Para [4, 9, 1, 6, 3] e k = 2: inverter tudo resulta em [3, 6, 1, 9, 4], inverter os dois primeiros resulta em [6, 3, 1, 9, 4], e inverter os três últimos resulta em [6, 3, 4, 9, 1].

Cada valor é trocado no máximo duas vezes, então o tempo é O(n) e a memória extra consiste em algumas variáveis de índice (O(n) em R, que copia o vetor quando o auxiliar de inversão o altera).

Algoritmo

Defina n como o comprimento de nums e substitua k por k mod n.
Inverta o array inteiro, dos índices 0 a n-1.
Inverta o primeiro bloco, dos índices 0 a k-1.
Inverta o segundo bloco, dos índices k a n-1.
Retorne nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Armadilhas e casos extremos

Esquecer k mod n. Com k = 10^9, rotacionar passo a passo nunca termina, e inverter os primeiros k valores acessa posições muito além do fim do array.
Fatiar sem aplicar o módulo. Em Python, nums[-k:] + nums[:-k] com k = 7 e n = 3 retorna o array inalterado, porque os dois recortes param no limite do array.
Inverter na ordem errada. Inverter os dois blocos primeiro e o array inteiro por último resulta em uma rotação à esquerda.
Erro de um na extremidade do bloco: o primeiro bloco termina no índice k-1 e o segundo começa em k. Em Lua e R, que contam a partir de 1, os blocos são 1..k e k+1..n.

Perguntas frequentes3

Qual é a complexidade de tempo de Rotate Array?

O(n) tanto para a abordagem de cópia quanto para as três inversões, porque cada valor é movido um número constante de vezes. Reduzir k com k mod n primeiro impede que um k enorme faça diferença. Rotacionar um passo de cada vez custa O(n × k).

O que acontece quando k é maior que o comprimento do array?

A cada n passos, o array volta à sua ordem inicial, então somente k mod n passos importam. Rotacionar [10, 20, 30] em 7 posições é o mesmo que rotacioná-lo em 1 posição, o que resulta em [30, 10, 20]. Quando k é múltiplo de n, o array não muda.

Como girar um array para a esquerda?

Uma rotação para a esquerda por k é uma rotação para a direita por n - (k mod n). Com reversões, inverta os primeiros k mod n valores, depois o restante e, por fim, o array inteiro. Ambos mantêm o tempo O(n).

def rotate(nums, k):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

nums = [4, 9, 1, 6, 3]
k = 2

Saída Esperada

[6, 3, 4, 9, 1]