Como implementar um método que revolucione uma Lista?

Programação
, ,
#1

O objetivo seria implementar um método rotate® que “gire” uma Lista para que o item de lista i se torne o item de lista (i + r) mod n.

Porém, quando executado em um ArrayDeque, ou um DualArrayDeque, rotate® deve ser executado em tempo O(1 + min{r, n − r}).

#2

Está meio confuso porque você o tópico tem a tag Python, mas você cita ArrayDeque que não existe nessa linguagem (em Python existe o deque).

Enfim, independente da linguagem: para rotacionar uma vez, basta pegar o último elemento e adicioná-lo no início. Então para rotacionar várias vezes, basta repetir esse processo.

Em Python seria assim:

from collections import deque

def rotate(d, r):
    for _ in range(r):
        d.appendleft(d.pop())

d = deque([1, 2, 3, 4, 5, 6])
rotate(d, 2)
print(d) # deque([5, 6, 1, 2, 3, 4])

Segundo esta tabela, as operações de append e pop são O(1), portanto a complexidade do algoritmo é O(‍r).

Claro, você pode otimizar um pouco mais. Se tiver 1000 elementos e você quiser rotacionar 998 posições, seria o mesmo que rotacionar 2 posições na “direção oposta”. Então poderia ser algo assim:

def rotate(d, r):
    if r < len(d) / 2:
        for _ in range(r):
            d.appendleft(d.pop())
    else:
        for _ in range(len(d) - r):
            d.append(d.popleft())

Ou seja, se r for menor que a metade do tamanho do deque, uso o algoritmo já usado acima (remove o último e adiciona no início). Caso contrário, eu faço na direção oposta: remove o primeiro e adiciona no final (mas a quantidade de vezes é o tamanho do deque menos r). Acho que isso garante a complexidade desejada.

2 curtidas