Einfügen und Verschieben der Matrix n * n

Question

Ich habe eine Matrix N * N.

Ich brauche eine Funktion zu implementieren, die num 0/1, legt es wird Matrix und zu prüfen, ob Zeile/Spalte mit allen 1.

Die Insertion sein müssen in dieser Reihenfolge ist: wenn die Matrix wie folgt aussehen:

0 1 0 
1 1 0 
0 0 0 

Und wir legen 1 so jetzt Matrix wie folgt aussehen:

1 0 1 
0 1 1 
0 0 0 

wenn wir jetzt 0 einsetzen, so dass die Matrix wie folgt aussieht:

0 1 0 
1 0 1 
1 0 0 

Ich habe die Idee, die rechte Verschiebung zur Matrix zu machen, und ich werde o (n^2) Zeit nehmen.

Es gibt eine andere Ideen, um die Funktion zu implementieren, die Wert (0/1) einfügen und überprüfen Sie für Zeile und Spalte mit allen 1?

Danke!

Answer 1

Eine Matrix üblicherweise als ein Array in einem Speicher, wobei jeder Speicherort (x,y) indexiert x*w + y implementiert ist, wo w die Breite des Arrays (xy und die Basis null). Das Drucken des Arrays ist so einfach wie das Einfügen einer neuen Zeile nach jeder w Elemente.

Dies macht einen Einsatz eine O(n) Operation. Verschieben Sie einfach jedes Element um eine Position im Array.