Spiral Matrix

MédioMatemática e simulação Arrays e strings

+10

Você recebe uma matriz de números inteiros com m linhas e n colunas, fornecida como uma lista de linhas. Retorne todos os seus valores em ordem espiral.

Comece no canto superior esquerdo e siga para a direita ao longo da linha superior, depois desça pela coluna da direita, siga para a esquerda ao longo da linha inferior e suba pela coluna da esquerda. Continue circulando para dentro no sentido horário até que cada valor tenha sido lido exatamente uma vez.

Função

spiralOrder(matrix: integer-2d-array) → integer-array

matrixinteger-2d-array: a grade de números inteiros, como uma lista de linhas de mesmo comprimento
Retornainteger-array: cada valor da matriz em ordem espiral no sentido horário, começando no canto superior esquerdo

Restrições

1 ≤ m, n ≤ 80, em que m = matrix.length e n = matrix[i].length
Cada linha tem o mesmo comprimento n.
-100 ≤ matrix[i][j] ≤ 100

Exemplos

Entrada: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Saída: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Explicação: Os valores aumentam ao longo da espiral. O anel externo mostra 1, 2, 3 na parte de cima, 4, 5, 6 descendo pelo lado direito, 7, 8 de volta pela parte de baixo e 9, 10 subindo pelo lado esquerdo. A camada interna é uma única coluna, lida uma vez de cima para baixo: 11, 12.

Entrada: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Saída: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Explicação: O anel externo fornece 7, 1, 5, 3, depois 6, -1 descendo pelo lado direito, 4, 0, 8 voltando pela parte inferior e 2 subindo pelo lado esquerdo. O que resta é a única linha 9, -4, lida uma vez da esquerda para a direita.

+15 testes ocultos ao enviar

Para ir além

Você pode retornar os valores em ordem anti-horária, começando no canto superior esquerdo e descendo primeiro pela coluna da esquerda?

Dicas

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

0 de 3 abertas

Solução

Não há matemática engenhosa aqui; o problema é manter o controle, e é aí que as soluções falham. Cada canto precisa ser lido uma vez, não duas, e a camada mais interna pode ser uma única linha ou uma única coluna, na qual uma volta completa passaria pelos mesmos valores novamente. Você pode percorrer a matriz como um robô que vira à direita sempre que encontra um bloqueio e se lembra de quais células já leu. Ou pode descascar a matriz um anel de cada vez, usando quatro limites que vão diminuindo, o que não exige memória extra.

Caminhe e vire à direita quando estiver bloqueado

Intuição

Imagine um caminhante na célula do canto superior esquerdo, voltado para a direita. Ele lê a célula em que está e, em seguida, tenta avançar. Se esse passo o levar para fora da matriz ou para uma célula que ele já leu, ele vira à direita (direita, baixo, esquerda, cima e, depois, direita novamente) e segue nessa direção. Essa regra desenha a espiral: as bordas da matriz encerram a primeira volta, e as células lidas até então funcionam como paredes em todas as voltas seguintes.

Mantenha a direção como um índice d em dois pequenos arrays, dr = [0, 1, 0, -1] e dc = [1, 0, -1, 0], de modo que virar à direita seja d = (d+1) % 4. Mantenha uma grade booleana seen do tamanho da matriz. No primeiro exemplo, o caminhante lê 1, 2, 3, encontra a borda direita e vira para baixo para ler 4, 5, 6, vira à esquerda para ler 7, 8 e para cima para ler 9, 10. Acima de 10 está o 1, já lido, então ele vira à direita e vai para 11. À direita de 11 está o 4, já lido, então ele vira para baixo e vai para 12.

Execute o loop exatamente m × n vezes, uma por célula, e você nunca precisará detectar o fim. Depois da última leitura, o caminhante pode estar voltado para uma parede, mas não dará mais nenhum passo. Cada célula é lida uma vez, então o tempo é O(m × n). A grade seen consome O(m × n) de memória extra, que a próxima abordagem elimina.

Algoritmo

Comece na linha 0, coluna 0, voltado para a direita, com uma grade seen totalmente falsa.
Repita m × n vezes: acrescente o valor atual e marque a célula como visitada.
Calcule a próxima célula na direção atual. Se estiver fora da matriz ou já tiver sido visitada, vire à direita e calcule novamente.
Mova-se para essa célula.
Retorne os valores na ordem em que foram acrescentados.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Descasque as camadas com quatro limites

Intuição

A espiral é um conjunto de anéis encaixados. Descreva o anel atual com quatro limites: linhas de top a bottom, colunas de left a right. Uma volta percorre a linha superior de left a right, a coluna da direita de top+1 até bottom, a linha inferior de right-1 de volta a left e a coluna da esquerda de bottom-1 até top+1. Cada lado começa uma célula depois do fim do lado anterior, então cada canto é lido exatamente uma vez. Depois, mova os quatro limites um passo para dentro e repita enquanto top ≤ bottom e left ≤ right.

A armadilha é um anel com apenas uma linha ou uma coluna de espessura, em que o caminho de volta passa por células já lidas. No segundo exemplo, depois do anel externo, os limites são top = bottom = 1, left = 1 e right = 2: a única linha 9, -4. A linha superior lê os dois valores, e a coluna da direita não tem nada abaixo de top. Mas a linha inferior é essa mesma linha, e percorrê-la de volta adicionaria 9 uma segunda vez. Portanto, percorra a linha inferior e a coluna da esquerda somente quando top < bottom e left < right. O terceiro exemplo é o caso inverso: na coluna única 4, 1, 7, percorrer a coluna da esquerda de volta para cima leria 1 novamente.

Cada valor é lido uma vez, então o tempo é O(m × n), o mínimo possível, já que a resposta contém todos os valores. Além da resposta, a memória usada é de quatro inteiros.

Algoritmo

Defina top = 0, bottom = m-1, left = 0, right = n-1.
Enquanto top ≤ bottom e left ≤ right, leia a linha superior de left até right e a coluna da direita de top+1 até bottom.
Se top < bottom e left < right, leia a linha inferior de right-1 até left e a coluna da esquerda de bottom-1 até top+1.
Some um a top e a left; subtraia um de bottom e de right.
Retorne os valores na ordem em que foram lidos.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Armadilhas e casos extremos

Os loops são curtos, então os bugs ficam nos cantos e na última camada.

Ler a última camada duas vezes quando ela tem uma linha ou uma coluna. Sem a verificação top < bottom e left < right, o segundo exemplo termina com 9, -4, 9 e o terceiro lê 4, 1, 7, 1.
Ler um canto duas vezes. Se cada lado vai da sua própria primeira célula até sua própria última célula, cada canto é lido por dois lados. Comece cada lado uma célula depois de onde o lado anterior terminou.
Usar um loop enquanto top < bottom em vez de top ≤ bottom. Isso para antes do meio de um quadrado de lado ímpar: em uma matriz 3 × 3, o valor central nunca é lido.
Confundir linhas e colunas em uma matriz que não é quadrada. Usar matrix.length para os dois limites funciona em todos os testes com matrizes quadradas e falha em uma matriz 3 × 4.
Esquecer as entradas estreitas: uma linha, uma coluna, uma célula. Cada uma é uma única camada que nunca chega à linha inferior nem à coluna esquerda.
Em R, a:b conta para baixo quando a > b, então um intervalo vazio, como 3:2, resulta em 3, 2 em vez de nada; proteja-o com uma condição ou use seq_len. Em Lua e R, as linhas e colunas começam em 1.

Perguntas frequentes4

Qual é a complexidade de tempo e espaço de Spiral Matrix?

As duas abordagens leem cada valor uma vez, então o tempo é O(m × n), e nenhuma solução pode ser melhor, pois a resposta contém todos os valores. Remover as camadas usando quatro limites requer O(1) de memória extra além da resposta. A caminhada que vira quando bloqueada usa uma grade O(m × n) para lembrar quais células já leu.

Como evitar ler um valor duas vezes em um percurso em espiral?

Dois pontos causam repetições. Nos cantos, comece cada lado uma célula depois de onde o lado anterior terminou, para que cada canto pertença a apenas um lado. Na última camada, leia a linha inferior e a coluna da esquerda somente quando a camada tiver mais de uma linha e mais de uma coluna, pois, caso contrário, o caminho de volta passa por células que você já leu.

Como preencher uma matriz em ordem espiral, em vez de percorrê-la?

Use os mesmos quatro limites e os mesmos quatro lados, mas escreva em vez de ler. Mantenha um contador que começa em 1 e armazene seu valor em cada célula à medida que avança, incrementando-o em um a cada vez. Para uma matriz n × n, o contador termina em n², e o primeiro exemplo acima é o resultado disso para uma grade 4 × 3.

Por que virar à direita quando estiver bloqueado produz uma espiral?

Na primeira volta, o caminhante vira nas quatro bordas da matriz. Em cada volta seguinte, as células percorridas antes funcionam como paredes, então cada volta vira uma célula antes do anel percorrido na volta anterior. Isso mantém cada volta dentro da anterior, formando a espiral. O caminhante nunca precisa saber em que camada está, apenas se a próxima célula está livre.

Python

def spiralOrder(matrix):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]

Esperado

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]