Spiral-Matrix-Algorithmus

Question

Ich habe Probleme bei der Berücksichtigung der ungeraden Eingabefälle im folgenden Problem: Gegeben einer Matrix von m x n Elementen (m Zeilen, n Spalten), alle Elemente der Matrix in der spiralförmigen Reihenfolge zurückgeben.

For example, 
Given the following matrix: 

[ 
[ 1, 2, 3 ], 
[ 4, 5, 6 ], 
[ 7, 8, 9 ] 
] 
You should return [1,2,3,6,9,8,7,4,5]. 

Mein Code funktioniert auf allen größeren Testfälle, aber nicht für Dinge wie

[[6,9,7]] 

und ich bin nicht sicher, wie mein Code zu konstruieren diese Eingaben zu verarbeiten. Hat jemand Ideen?

def spiral_order(matrix) 
    return nil if matrix.nil? 
    return [] if matrix.empty? 
    m = matrix.length - 1 
    n = matrix.first.length - 1 
    start_col = start_row = 0 
    end_col = n 
    end_row = m 
    visited = [] 
    iter = 0 
    until start_row > end_row && start_col > end_col 
     until iter > end_col 
      visited << matrix[start_row][iter] 
      iter+=1 
     end 
     start_row += 1 
     iter = start_row 

     until iter > end_row 
      visited << matrix[iter][end_col] 
      iter += 1 
     end 
     end_col -= 1 
     iter = end_col 

     until iter < start_col 
      visited << matrix[end_row][iter] 
      iter-=1 
     end 
     end_row -= 1 
     iter = end_row 

     until iter < start_row 
      visited << matrix[iter][start_col] 
      iter -= 1 
     end 
     start_col += 1 
     iter = start_col 
    end 

    visited 
end 

Auf die [6,9,7] Ich bin ein Null-Fehler immer auf Linie 17. Ich kenne die gesamte Schleife läuft zweimal (dies allein sollte nicht der Fall sein, weil ich das Erhöhen bin Startlimits und Dekrementieren der Endlimits), aber ich habe Mühe, einen Code zu erstellen, der sowohl für reguläre Eingaben als auch für die seltsamen Fälle funktioniert, ohne eine Tonne an Bedingungen einzuwerfen, um mit ungewöhnlicheren Fällen fertig zu werden.

Answer 1

Dies kann mit einem viel einfacheren Satz von Code angesprochen werden. Streifen Sie die obere Reihe von der Matrix ab, drehen Sie die Matrix, wiederholen Sie, bis sie leer ist.

def spiral_order(matrix) 
    m = matrix.dup 
    result = [] 
    until m.size < 1 
    result << m.shift 
    m = m.transpose.reverse 
    end 
    result.flatten 
end 

>> matrix = [[1,2,3],[4,5,6],[7,8,9]] 
>> spiral_order(matrix) 
=> [1, 2, 3, 6, 9, 8, 7, 4, 5] 

>> matrix = [[6,9,7]] 
>> spiral_order(matrix) 
=> [6, 9, 7] 

Wenn Sie mit großen Matrizen arbeiten und wollen mehrere Doppelungen zu vermeiden, für ein wenig zusätzliche Komplexität, dies zu tun:

def spiral_order(matrix) 
    m = matrix.map(&:dup) 
    result = [] 
    until m.size < 1 
    result << m.shift 
    result << m.map(&:pop) 
    result << (m.pop || []).reverse 
    result << m.map(&:shift).reverse 
    end 
    result.flatten.compact 
end 

Der Algorithmus funktioniert wie folgt: Linie 2 tief Duplikate Die Matrix, so dass das Original übergeben wird, ist unberührt. Zeile 5 streift die obere Reihe ab. Zeile 6 streift die rechte Spalte ab. Zeile 7 streift die untere Reihe ab und dreht sie um. (Die || [] stellt sicher, dass wir #reverse nicht mit einem Nullwert aufrufen.) Zeile 8 streift die linke Spalte ab und kehrt sie um. Die Zeilen 5-8 werden wiederholt, bis die Matrix leer ist. An diesem Punkt entfernt Zeile 10 interne Arrays und Nils und gibt das Ergebnis zurück.