Set jede Zelle in der Matrix auf 0, wenn diese Zeile oder Spalte ein 0 enthält,
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
eine NxN-Matrix mit 0 und 1 gegeben. Legen Sie jede Zeile, die eine 0 auf alle 0s enthält und stellen Sie jede Spalte, die einen 0 allen 0s enthält.
Zum Beispiel
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
Ergebnisse in
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
Ein Microsoft-Ingenieur sagte mir, dass es eine Lösung gibt, die keinen zusätzlichen Speicher, nur zwei Booleschen Variablen und einen Durchgang, so suche ich nach dieser Antwort beinhaltet.
BTW, sich vorstellen, es ist ein bisschen Matrix, also nur 1 und 0 sind damit in der Matrix sein.
Lösung
Ok, ich bin so müde, wie es 03.00 ist hier, aber ich habe einen ersten Versuch Inplace mit genau 2 Durchgängen auf jede Zahl in der Matrix, so in O (N · N), und es ist linear in der Größe der Matrix.
I 1rst Spalte und ersten Zeile als Marker verwenden zu wissen, wo sind Zeilen / Spalten mit nur 1 ist. Dann gibt es zwei Variablen l und c zu erinnern, wenn 1rst Zeile / Spalte auch die alle 1 sind. So der erste Durchlauf werden die Markierungen und setzt den Rest auf 0 ist.
Der zweite Durchgang Sätze 1 an Orten, wo Zeilen und Spalten markiert, wobei 1 zu sein, und setzt 1.e Zeile / Spalte in Abhängigkeit von l und c.
Ich bezweifle stark, dass ich in 1 Durchgang durchgeführt werden kann als Quadrate am Anfang auf den Plätze am Ende ab. Vielleicht kann mein zweiter Pass effizienter gemacht werden ...
import pprint
m = [[1, 0, 1, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1]]
N = len(m)
### pass 1
# 1 rst line/column
c = 1
for i in range(N):
c &= m[i][0]
l = 1
for i in range(1,N):
l &= m[0][i]
# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
for j in range(1,N):
if m[i][j] == 0:
m[0][j] = 0
m[i][0] = 0
else:
m[i][j] = 0
### pass 2
# if line1 and col1 are ones: it is 1
for i in range(1,N):
for j in range(1,N):
if m[i][0] & m[0][j]:
m[i][j] = 1
# 1rst row and col: reset if 0
if l == 0:
for i in range(N):
m [i][0] = 0
if c == 0:
for j in range(1,N):
m [0][j] = 0
pprint.pprint(m)
Andere Tipps
Das kann nicht in einem Arbeitsgang durchgeführt werden, da ein einzelnes Bit eine Wirkung auf die Bits vor und nach in irgendeiner Reihenfolge hat. IOW Was auch immer Ihnen die Array in Traverse, später eine 0 kommen über können, was bedeutet, müssen Sie eine vorherige 1 auf eine 0 zurück und ändern gehen.
Update
Die Leute scheinen zu denken, dass N zu einem festen Wert durch die Beschränkung (etwa 8) können Sie lösen diese einen Durchlauf ist. Nun, das ist a) fehlt den Punkt und b) nicht die ursprüngliche Frage. Ich würde nicht eine Frage stellen auf Sortieren und erwarten eine Antwort, die der Autor „vorausgesetzt, Sie wollen nur sortieren 8 Dinge ...“.
Wie gesagt, es ist ein sinnvoller Ansatz, wenn Sie wissen, dass N in der Tat bis 8. Meine Antwort oben beschränkt ist, die ursprüngliche Frage beantwortet, die keine derartige retriction hat.
Also meine Idee ist es, die Werte in der letzten Zeile / Spalte als Flag zu verwenden, um anzuzeigen, ob alle Werte in der entsprechenden Spalte / Zeile sind 1s.
Mit einem Zig Zag Scan durch die gesamte Matrix AUSSER die letzte Zeile / Spalte. Bei jedem Element, setzen Sie den Wert in der letzten Zeile / Spalte in Bezug auf die logische UND-Verknüpfung sich mit dem Wert in dem aktuellen Element. Mit anderen Worten, wenn Sie eine 0 getroffen, wird die letzte Zeile / Spalte auf 0 gesetzt werden, wenn Sie es sich um eine 1, wird der Wert in der letzten Zeile / Spalte 1 nur, wenn es 1 ohnehin schon war. In jedem Fall stellen Sie das aktuelle Element auf 0.
Wenn Sie fertig sind, Ihre letzte Zeile / Spalte sollte 1s haben iff die entsprechende Spalte / Zeile mit 1s gefüllt wurde.
Führen Sie eine lineare Abtastung durch die letzte Zeile und Spalte und die Suche nach 1s. Set 1s in die entsprechenden Elemente in Körper der Matrix, wo die letzte Zeile und Spalte sind beide 1s.
Coding es schwierig sein wird, Off-by-one Fehler zu vermeiden, usw., aber es sollte in einem Durchgang arbeiten.
Ich habe hier eine Lösung habe, läuft es in einem einzigen Durchgang, und zwar die gesamte Verarbeitung „in place“ ohne zusätzliche Speicher (speichern für den Anbau des Stack).
Es verwendet Rekursion das Schreiben von Nullen zu verzögern, was natürlich die Matrix für die anderen Reihen zerstören würde und cols:
#include <iostream>
/**
* The idea with my algorithm is to delay the writing of zeros
* till all rows and cols can be processed. I do this using
* recursion:
* 1) Enter Recursive Function:
* 2) Check the row and col of this "corner" for zeros and store the results in bools
* 3) Send recursive function to the next corner
* 4) When the recursive function returns, use the data we stored in step 2
* to zero the the row and col conditionally
*
* The corners I talk about are just how I ensure I hit all the row's a cols,
* I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n).
*
* For simplicities sake, I use ints instead of individual bits. But I never store
* anything but 0 or 1 so it's still fair ;)
*/
// ================================
// Using globals just to keep function
// call syntax as straight forward as possible
int n = 5;
int m[5][5] = {
{ 1, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }
};
// ================================
// Just declaring the function prototypes
void processMatrix();
void processCorner( int cornerIndex );
bool checkRow( int rowIndex );
bool checkCol( int colIndex );
void zeroRow( int rowIndex );
void zeroCol( int colIndex );
void printMatrix();
// This function primes the pump
void processMatrix() {
processCorner( 0 );
}
// Step 1) This is the heart of my recursive algorithm
void processCorner( int cornerIndex ) {
// Step 2) Do the logic processing here and store the results
bool rowZero = checkRow( cornerIndex );
bool colZero = checkCol( cornerIndex );
// Step 3) Now progress through the matrix
int nextCorner = cornerIndex + 1;
if( nextCorner < n )
processCorner( nextCorner );
// Step 4) Finially apply the changes determined earlier
if( colZero )
zeroCol( cornerIndex );
if( rowZero )
zeroRow( cornerIndex );
}
// This function returns whether or not the row contains a zero
bool checkRow( int rowIndex ) {
bool zero = false;
for( int i=0; i<n && !zero; ++i ) {
if( m[ rowIndex ][ i ] == 0 )
zero = true;
}
return zero;
}
// This is just a helper function for zeroing a row
void zeroRow( int rowIndex ) {
for( int i=0; i<n; ++i ) {
m[ rowIndex ][ i ] = 0;
}
}
// This function returns whether or not the col contains a zero
bool checkCol( int colIndex ) {
bool zero = false;
for( int i=0; i<n && !zero; ++i ) {
if( m[ i ][ colIndex ] == 0 )
zero = true;
}
return zero;
}
// This is just a helper function for zeroing a col
void zeroCol( int colIndex ) {
for( int i=0; i<n; ++i ) {
m[ i ][ colIndex ] = 0;
}
}
// Just a helper function for printing our matrix to std::out
void printMatrix() {
std::cout << std::endl;
for( int y=0; y<n; ++y ) {
for( int x=0; x<n; ++x ) {
std::cout << m[y][x] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}
// Execute!
int main() {
printMatrix();
processMatrix();
printMatrix();
}
Ich glaube nicht, es ist machbar. Wenn Sie auf dem ersten Platz sind und deren Wert 1 ist, haben Sie keine Möglichkeit zu wissen, was die Werte der anderen Plätzen in der gleichen Zeile und Spalte sind. Sie müssen also diejenigen überprüfen und, wenn es eine Null ist, kehrt zum ersten Platz und den Wert auf Null ändern. Ich werde tun, es in zwei Durchgängen empfehlen - der erste Durchgang Informationen sammelt, über die Zeilen und Spalten auf Null gestellt werden muss aus (die Information in einem Array gespeichert ist, so dass wir mit etwas mehr Speicher). Der zweite Durchlauf ändert die Werte. Ich weiß, das ist nicht die Lösung, die Sie suchen, aber ich denke, es ist ein praktischer. Die Einschränkungen gegeben durch Sie machen das Problem unlösbar.
Ich kann es mit zwei Integer-Variablen und zwei Durchgängen (bis zu 32 Zeilen und Spalten ...)
bool matrix[5][5] =
{
{1, 0, 1, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1}
};
int CompleteRows = ~0;
int CompleteCols = ~0;
// Find the first 0
for (int row = 0; row < 5; ++row)
{
for (int col = 0; col < 5; ++col)
{
CompleteRows &= ~(!matrix[row][col] << row);
CompleteCols &= ~(!matrix[row][col] << col);
}
}
for (int row = 0; row < 5; ++row)
for (int col = 0; col < 5; ++col)
matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col));
Das Problem kann in einem Durchgang gelöst werden
Speicher die Matrix in einem i X j-Array.
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
one each pass save the values of i and j for an element which is 0 in arrays a and b
when first row is scanned a= 1 b = 2,5
when second row is scanned a=1,2 b= 1,2,5
when third row is scanned no change
when fourth row is scanned a= 1,2,4 and b= 1,2,5
when fifth row is scanned no change .
jetzt alle Werte als 0 für Werte von i und j drucken in a und b gespeichert restliche Werte sind 1, dh (3,3) (3,4) (5,3) und (5,4)
Eine weitere Lösung, die zwei Durchgänge stattfindet, ist ANDs horizontal und vertikal zu akkumulieren:
1 0 1 1 0 | 0
0 1 1 1 0 | 0
1 1 1 1 1 | 1
1 0 1 1 1 | 0
1 1 1 1 1 | 1
----------+
0 0 1 1 0
Ich dachte, ich einen solchen Algorithmus konstruieren könnte mit Paritätsbits Hamming-Codes oder dynamische Programmierung , mit möglicherweise diese beiden booleans als 2-Bit-Zahl, aber ich habe keinen Erfolg noch.
Können Sie bitte die Problemstellung mit Ihrem Ingenieur erneut überprüfen und lassen Sie uns wissen? Wenn es ist in der Tat eine Lösung, ich möchte auf das Problem halten kratzen.
eine einzelne Variable Behalten Sie den Überblick zu behalten, was alle Zeilen verknüpft sind zusammen.
Wenn eine Zeile -1 (alle 1 s), dann die nächste Zeile zu diesen Variablen eine Referenz machen
Wenn eine Zeile etwas ist aber, es ist ein 0. Sie alles in einem Arbeitsgang tun. Psuedo-Code:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
Das sollte es tun, in einem einzigen Durchgang - aber es ist eine Annahme, hier, dass N klein genug ist, um für die CPU Arithmetik auf einer einzige Zeile zu tun, sonst wirst du Schleife über jede Zeile müssen, um zu bestimmen wenn sie alle 1s ist oder nicht, glaube ich. Aber da Sie algos sind gefragt und meine Hardware nicht beschränke, würde ich nur meine Antwort beginnen mit „Aufbau einer CPU, die N-Bit-Arithmetik unterstützt ...“
Hier ist ein Beispiel wie es in C erfolgen Hinweis ich argumentieren, dass Werte und arr zusammen das Array repräsentieren genommen, und p und numproduct sind meine Iterator und und Produktvariablen, um das Problem zu implementieren. (I mit Zeigerarithmetik durchgeschleift über arr konnte meine Arbeit zu validieren, aber einmal war genug!)
int main() {
int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */
int *arr[5] = { values, values+1, values+2, values+3, values+4 };
int **p;
int numproduct = 127;
for(p = arr; p < arr+5; ++p) {
numproduct = numproduct & **p;
if(**p != -1) {
**p = 0;
} else {
*p = &numproduct;
}
}
/* Print our array, this loop is just for show */
int i;
for(i = 0; i < 5; ++i) {
printf("%x\n",*arr[i]);
}
return 0;
}
Dies erzeugt 0, 0, 6, 0, 6, die das Ergebnis für die gegebenen Eingänge ist.
oder in PHP, wenn die Leute meinen Stack Spiele in C denken betrügen (Ich schlage vor, Sie, dass es nicht, weil ich in der Lage sein sollte, die Matrix zu speichern, je nachdem, wie ich bitte):
<?php
$values = array(-10, 14, -1, -9, -1);
$numproduct = 127;
for($i = 0; $i < 5; ++$i) {
$numproduct = $numproduct & $values[$i];
if($values[$i] != -1) {
$values[$i] = 0;
} else {
$values[$i] = &$numproduct;
}
}
print_r($values);
Bin ich etwas fehlt?
Nizza challange. Diese Lösung Art verwendet nur zwei booleans auf dem Stapel erstellt, aber die booleans werden mehrmals auf dem Stapel erstellt, da die Funktion rekursiv ist.
typedef unsigned short WORD;
typedef unsigned char BOOL;
#define true 1
#define false 0
BYTE buffer[5][5] = {
1, 0, 1, 1, 0,
0, 1, 1, 1, 0,
1, 1, 1, 1, 1,
1, 0, 1, 1, 1,
1, 1, 1, 1, 1
};
int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N)
{
WORD i;
for(i=0;i<N;i++)
{
if(!buffer[i][pos_N])
*h=false;
if(!buffer[pos_N][i])
*w=false;
}
return 0;
}
int set_line(BOOL h,BOOL w,WORD N,WORD pos_N)
{
WORD i;
if(!h)
for(i=0;i<N;i++)
buffer[i][pos_N] = false;
if(!w)
for(i=0;i<N;i++)
buffer[pos_N][i] = false;
return 0;
}
int scan(int N,int pos_N)
{
BOOL h = true;
BOOL w = true;
if(pos_N == N)
return 0;
// Do single scan
scan_to_end(&h,&w,N,pos_N);
// Scan all recursive before changeing data
scan(N,pos_N+1);
// Set the result of the scan
set_line(h,w,N,pos_N);
return 0;
}
int main(void)
{
printf("Old matrix\n");
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
scan(5,0);
printf("New matrix\n");
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
system( "pause" );
return 0;
}
Diese scannt in einem Muster wie:
s,s,s,s,s
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
0,s,0,0,0
s,s,s,s,s
0,s,0,0,0
0,s,0,0,0
0,s,0,0,0
und so weiter
Und dann changeing die Werte in diesem Muster auf Rückkehr auf jedem der Scanfunktionen. (Bottom-up):
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
c,c,c,c,c
0,0,0,c,0
0,0,0,c,0
0,0,0,c,0
c,c,c,c,c
0,0,0,c,0
und so weiter
Okay, das ist eine Lösung, die
- verwendet nur einen extra langen Wert für die Lagerung arbeiten.
- verwendet keine Rekursion.
- ein Durchlauf von nur N, nicht einmal N * N.
- wird für andere Werte von N arbeiten, aber neuen #defines benötigen.
#include <stdio.h> #define BIT30 (1<<24) #define COLMASK 0x108421L #define ROWMASK 0x1fL
unsigned long long STARTGRID =
((0x10 | 0x0 | 0x4 | 0x2 | 0x0) << 20) |
((0x00 | 0x8 | 0x4 | 0x2 | 0x0) << 15) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 10) |
((0x10 | 0x0 | 0x4 | 0x2 | 0x1) << 5) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 0);
void dumpGrid (char* comment, unsigned long long theGrid) {
char buffer[1000];
buffer[0]='\0';
printf ("\n\n%s\n",comment);
for (int j=1;j<31; j++) {
if (j%5!=1)
printf( "%s%s", ((theGrid & BIT30)==BIT30)? "1" : "0",(((j%5)==0)?"\n" : ",") );
theGrid = theGrid << 1;
}
}
int main (int argc, const char * argv[]) {
unsigned long long rowgrid = STARTGRID;
unsigned long long colGrid = rowgrid;
unsigned long long rowmask = ROWMASK;
unsigned long long colmask = COLMASK;
dumpGrid("Initial Grid", rowgrid);
for (int i=0; i<5; i++) {
if ((rowgrid & rowmask)== rowmask) rowgrid |= rowmask;
else rowgrid &= ~rowmask;
if ((colGrid & colmask) == colmask) colmask |= colmask;
else colGrid &= ~colmask;
rowmask <<= 5;
colmask <<= 1;
}
colGrid &= rowgrid;
dumpGrid("RESULT Grid", colGrid);
return 0;
}
Eigentlich. Wenn Sie nur den Algorithmus ausgeführt werden sollen und die Ergebnisse ausdrucken (dh sie nicht gestellt werden, dann kann dies leicht in einem Durchgang durchgeführt werden. Das Problem kommt, wenn Sie versuchen, das Array zu ändern, wie Sie den Algorithmus ausführen.
Hier ist meine Lösung Es handelt sich nur ANDing die Zeilen / Spalten-Werte für eine givein (i, j) 's Element und druckt.
#include <iostream>
#include "stdlib.h"
void process();
int dim = 5;
bool m[5][5]{{1,0,1,1,1},{0,1,1,0,1},{1,1,1,1,1},{1,1,1,1,1},{0,0,1,1,1}};
int main() {
process();
return 0;
}
void process() {
for(int j = 0; j < dim; j++) {
for(int i = 0; i < dim; i++) {
std::cout << (
(m[0][j] & m[1][j] & m[2][j] & m[3][j] & m[4][j]) &
(m[i][0] & m[i][1] & m[i][2] & m[i][3] & m[i][4])
);
}
std::cout << std::endl;
}
}
Ich habe versucht, dieses Problem in C # zu lösen.
Ich habe zwei Schleifenvariablen (i und j) abgesehen von der tatsächlichen Matrix verwendet und n seiner Dimension repräsentierte
Logik Ich habe versucht, zu:
- berechnen und für Reihen und in jedem konzentrischen Quadrat der Matrix beteiligt cols
- Bewahren Sie es in seiner Ecke Zellen (ich habe sie in gegen den Uhrzeigersinn, um gespeichert)
- Zwei Bool Variablen werden verwendet, um Werte von zwei Ecken zu halten, wenn ein bestimmtes Quadrat auswertet.
- Dieser Prozess würde enden, wenn äußere Schleife (i) auf halbem Weg ist.
- Ausrechnen Ergebnisse anderer an der Ecke Zellen basierte Zellen (für die Erholung von i). Überspringen Sie die Ecke Zellen während dieses Prozesses.
- Wenn i n erreicht, werden alle Zellen würden ihr Ergebnis haben mit Ausnahme der Ecke Zellen.
- Aktualisieren Sie die Ecke Zellen. Dies ist eine zusätzliche Iteration Länge von n / 2 anders als die einzigen Einschränkung Pass in dem Problem erwähnt.
Code:
void Evaluate(bool [,] matrix, int n)
{
bool tempvar1, tempvar2;
for (var i = 0; i < n; i++)
{
tempvar1 = matrix[i, i];
tempvar2 = matrix[n - i - 1, n - i - 1];
var j = 0;
for (j = 0; j < n; j++)
{
if ((i < n/2) || (((n % 2) == 1) && (i == n/2) && (j <= i)))
{
// store the row and col & results in corner cells of concentric squares
tempvar1 &= matrix[j, i];
matrix[i, i] &= matrix[i, j];
tempvar2 &= matrix[n - j - 1, n - i - 1];
matrix[n - i - 1, n - i - 1] &= matrix[n - i - 1, n - j - 1];
}
else
{
// skip corner cells of concentric squares
if ((j == i) || (j == n - i - 1)) continue;
// calculate the & values for rest of them
matrix[i, j] = matrix[i, i] & matrix[n - j - 1, j];
matrix[n - i - 1, j] = matrix[n - i - 1, n - i - 1] & matrix[n - j - 1, j];
if ((i == n/2) && ((n % 2) == 1))
{
// if n is odd
matrix[i, n - j - 1] = matrix[i, i] & matrix[j, n - j - 1];
}
}
}
if ((i < n/2) || (((n % 2) == 1) && (i <= n/2)))
{
// transfer the values from temp variables to appropriate corner cells of its corresponding square
matrix[n - i - 1, i] = tempvar1;
matrix[i, n - i - 1] = tempvar2;
}
else if (i == n - 1)
{
// update the values of corner cells of each concentric square
for (j = n/2; j < n; j++)
{
tempvar1 = matrix[j, j];
tempvar2 = matrix[n - j - 1, n - j - 1];
matrix[j, j] &= matrix[n - j - 1, j];
matrix[n - j - 1, j] &= tempvar2;
matrix[n - j - 1, n - j - 1] &= matrix[j, n - j - 1];
matrix[j, n - j - 1] &= tempvar1;
}
}
}
}
Während unmöglich die Einschränkungen gegeben, die platzsparende Art und Weise, es zu tun ist durch die Matrix in einer overlaping durchqueren, abwechselnd Zeilen / Spalten-Mode, die ein ähnliches Muster wie bei Verlegung Ziegel in einer Zick-Zack-Weise machen würde:
-----
|----
||---
|||--
||||-
diese verwenden, würden Sie in jeder Zeile / Spalte gehen, wie angegeben, und wenn Sie eine 0 jederzeit auftreten, stellen Sie eine boolean Variable, und wieder gehen, dass die Zeile / Spalte, die Einträge auf 0 setzen, wie Sie gehen .
Dies wird keinen zusätzlichen Speicher benötigen, und wird nur eine boolean Variable verwenden. Leider, wenn der „weit“ Rand auf all 0 sein gesetzt, das ist der schlimmste Fall und man zu Fuß das gesamte Array zweimal.
eine Ergebnismatrix erstellen und alle Werte auf 1 gesetzt. die Datenmatrix durchlaufen, sobald ein 0 angetroffen wird, das Ergebnis Matrixzeile Spalte auf 0 gesetzt
Am Ende des ersten Durchgangs, die Ergebnismatrix wird die richtige Antwort hat.
Sieht ziemlich einfach. Gibt es einen Trick, den ich fehle? Sie sind nicht erlaubt, eine Ergebnismenge zu benutzen?
EDIT:
Sieht aus wie eine # Funktion F, aber das ist ein bisschen zu betrügen, da, obwohl Sie einen einzigen Durchlauf tun, kann die Funktion rekursiv sein.
Es sieht aus wie der Interviewer, um herauszufinden versucht, ob Sie funktionale Programmierung kennen.
Nun, ich kam mit einer Single-Pass-up, an Ort und Stelle (nicht rekursiv) Lösung unter Verwendung von 4 bools und 2 Schleifenzählern. Ich habe nicht reduzieren sie auf 2 bools und 2 Ints geschaffen, aber ich wäre nicht überrascht, wenn es möglich wäre. Es tut um 3 liest und 3 schreibt jeder Zelle, und es sollte O (N ^ 2), dh sein. linear in der Array-Größe.
Hat mich ein paar Stunden, dieses zu enträtseln - ich würde nicht mit ihm unter dem Druck eines Interviews zu kommen haben wollen! Wenn ich eine booboo gemacht habe bin ich zu müde, um es zu erkennen ...
Um ... Ich wähle „Single-Pass“, wie die Herstellung einer Sweep durch die Matrix zu definieren, anstatt jeden Wert einmal zu berühren! : -)
#include <stdio.h>
#include <memory.h>
#define SIZE 5
typedef unsigned char u8;
u8 g_Array[ SIZE ][ SIZE ];
void Dump()
{
for ( int nRow = 0; nRow < SIZE; ++nRow )
{
for ( int nColumn = 0; nColumn < SIZE; ++nColumn )
{
printf( "%d ", g_Array[ nRow ][ nColumn ] );
}
printf( "\n" );
}
}
void Process()
{
u8 fCarriedAlpha = true;
u8 fCarriedBeta = true;
for ( int nStep = 0; nStep < SIZE; ++nStep )
{
u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true;
u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true;
fAlpha &= g_Array[ nStep ][ nStep ];
fBeta &= g_Array[ nStep ][ nStep ];
g_Array[ nStep-1 ][ nStep ] = fCarriedBeta;
g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha;
for ( int nScan = nStep + 1; nScan < SIZE; ++nScan )
{
fBeta &= g_Array[ nStep ][ nScan ];
if ( nStep > 0 )
{
g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ];
g_Array[ nStep-1][ nScan ] = fCarriedBeta;
}
fAlpha &= g_Array[ nScan ][ nStep ];
if ( nStep > 0 )
{
g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ];
g_Array[ nScan ][ nStep-1] = fCarriedAlpha;
}
}
g_Array[ nStep ][ nStep ] = fAlpha & fBeta;
for ( int nScan = nStep - 1; nScan >= 0; --nScan )
{
g_Array[ nScan ][ nStep ] &= fAlpha;
g_Array[ nStep ][ nScan ] &= fBeta;
}
fCarriedAlpha = fAlpha;
fCarriedBeta = fBeta;
}
}
int main()
{
memset( g_Array, 1, sizeof(g_Array) );
g_Array[0][1] = 0;
g_Array[0][4] = 0;
g_Array[1][0] = 0;
g_Array[1][4] = 0;
g_Array[3][1] = 0;
printf( "Input:\n" );
Dump();
Process();
printf( "\nOutput:\n" );
Dump();
return 0;
}
ich hoffe, dass Sie meine 1-pass c # Lösung genießen
Sie können ein Element mit O (1) und nur Notwendigkeit abrufen der Raum, der eine Zeile und eine Spalte der Matrix
bool[][] matrix =
{
new[] { true, false, true, true, false }, // 10110
new[] { false, true, true, true, false }, // 01110
new[] { true, true, true, true, true }, // 11111
new[] { true, false, true, true, true }, // 10111
new[] { true, true, true, true, true } // 11111
};
int n = matrix.Length;
bool[] enabledRows = new bool[n];
bool[] enabledColumns = new bool[n];
for (int i = 0; i < n; i++)
{
enabledRows[i] = true;
enabledColumns[i] = true;
}
for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
for (int columnIndex = 0; columnIndex < n; columnIndex++)
{
bool element = matrix[rowIndex][columnIndex];
enabledRows[rowIndex] &= element;
enabledColumns[columnIndex] &= element;
}
}
for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
for (int columnIndex = 0; columnIndex < n; columnIndex++)
{
bool element = enabledRows[rowIndex] & enabledColumns[columnIndex];
Console.Write(Convert.ToInt32(element));
}
Console.WriteLine();
}
/*
00000
00000
00110
00000
00110
*/
1 Durchgang, 2 booleans. Ich muß nur den Integer-Indizes in den Iterationen nicht davon ausgehen, zählen.
Dies ist keine vollständige Lösung, aber ich kann nicht diesen Punkt passieren.
Wenn ich könnte nur feststellen, ob ein 0 ein Original 0 oder ein 1 ist, der mit einem 0 umgewandelt wurde, dann würde ich nicht verwenden, um -1 ist und dies funktionieren würde.
Meine Ausgabe ist wie folgt:
-1 0 -1 -1 0
0 -1 -1 -1 0
-1 -1 1 1 -1
-1 0 -1 -1 -1
-1 -1 1 1 -1
Die Originalität meines Ansatzes wird mit der ersten Hälfte der Prüfung einer Zeile oder Spalte, um zu bestimmen, ob es ein 0 und die letzte Hälfte enthält die Werte zu setzen - dies durch einen Blick auf x und Breite x durchgeführt wird und dann y-y und die Höhe in jeder Iteration. Basierend auf den Ergebnissen der ersten Hälfte der Iteration, wenn ein 0 in der Zeile oder Spalte gefunden wurde, verwende ich die letzte Hälfte der Iteration auf -1 ist die 1en zu ändern.
Ich könnte dies nur Realisiert mit geschähe nur 1 boolean verlassen 1 bis ...?
Ich bin Entsendung diese Hoffnung, jemand könnte sagen: „Ah, genau dies zu tun ...“ (Und ich verbrachte viel zu viel Zeit auf sie nicht zu veröffentlichen.)
Hier ist der Code in VB:
Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}}
Dim B1, B2 As Boolean
For y As Integer = 0 To UBound(D)
B1 = True : B2 = True
For x As Integer = 0 To UBound(D)
// Scan row for 0's at x and width - x positions. Halfway through I'll konw if there's a 0 in this row.
//If a 0 is found set my first boolean to false.
If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False
End If
//If the boolean is false then a 0 in this row was found. Spend the last half of this loop
//updating the values. This is where I'm stuck. If I change a 1 to a 0 it will cause the column
//scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if
//the value had changed this would work.
If Not B1 Then
If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(x, y) = 1 Then D(x, y) = -1
If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1
End If
End If
//These 2 block do the same as the first 2 blocks but I switch x and y to do the column.
If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False
End If
If Not B2 Then
If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(y, x) = 1 Then D(y, x) = -1
If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1
End If
End If
Next
Next
Niemand Binärformat verwendet? da es nur 1 und 0 ist Wir können binäre Vektoren verwendet werden.
def set1(M, N):
'''Set 1/0s on M according to the rules.
M is a list of N integers. Each integer represents a binary array, e.g.,
000100'''
ruler = 2**N-1
for i,v in enumerate(M):
ruler = ruler & M[i]
M[i] = M[i] if M[i]==2**N-1 else 0 # set i-th row to all-0 if not all-1s
for i,v in enumerate(M):
if M[i]: M[i] = ruler
return M
Hier ist der Test:
M = [ 0b10110,
0b01110,
0b11111,
0b10111,
0b11111 ]
print "Before..."
for i in M: print "{:0=5b}".format(i)
M = set1(M, len(M))
print "After..."
for i in M: print "{:0=5b}".format(i)
Und die Ausgabe:
Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
Sie können etwas tun einen Durchlauf zu verwenden, sondern eine Ein- und Ausgangsmatrix:
output(x,y) = col(xy) & row(xy) == 2^n
wobei col(xy) ist die Bits in der Spalte, die den Punkt xy enthält; row(xy) ist der Bits in der Zeile mit der Nummer xy. n ist die Größe der Matrix.
Dann einfach Schleife über den Eingang. Möglicherweise erweiterbar mehr Platz effizient zu sein?
Eine Matrix-Scan, zwei booleans, keine Rekursion.
Wie den zweiten Durchgang zu vermeiden? Der zweite Durchlauf benötigt wird, um die Zeilen oder Spalten zu löschen, wenn die Null an ihrem Ende appeares.
Allerdings kann dieses Problem gelöst werden, denn wenn wir Reihe scannen #i wir bereits die Zeile Status für die Zeile # weiß i-1. Während wir also die Reihe #i scannen können wir gleichzeitig die Zeile # löschen i-1, wenn es gebraucht wird.
Die gleiche Lösung arbeitet für Spalten, aber wir müssen Zeilen und Spalten scannen gleichzeitig, während die Daten nicht von der nächsten Iteration geändert werden.
Zwei booleans sind erforderlich, um den Status der ersten Reihe und der ersten Spalte zu speichern, weil ihre Werte während der Ausführung des Hauptteils des Algorithmus geändert werden.
Um zu vermeiden, mehr booleans Zugabe wir den „clear“ Flag für die Zeilen und Spalten in der ersten Zeile und Spalte der Matrix zu speichern.
public void Run()
{
const int N = 5;
int[,] m = new int[N, N]
{{ 1, 0, 1, 1, 0 },
{ 1, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }};
bool keepFirstRow = (m[0, 0] == 1);
bool keepFirstColumn = keepFirstRow;
for (int i = 1; i < N; i++)
{
keepFirstRow = keepFirstRow && (m[0, i] == 1);
keepFirstColumn = keepFirstColumn && (m[i, 0] == 1);
}
Print(m); // show initial setup
m[0, 0] = 1; // to protect first row from clearing by "second pass"
// "second pass" is performed over i-1 row/column,
// so we use one more index just to complete "second pass" over the
// last row/column
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
// "first pass" - searcing for zeroes in row/column #i
// when i = N || j == N it is additional pass for clearing
// the previous row/column
// j >= i because cells with j < i may be already modified
// by "second pass" part
if (i < N && j < N && j >= i)
{
m[i, 0] &= m[i, j];
m[0, j] &= m[i, j];
m[0, i] &= m[j, i];
m[j, 0] &= m[j, i];
}
// "second pass" - clearing the row/column scanned
// in the previous iteration
if (m[i - 1, 0] == 0 && j < N)
{
m[i - 1, j] = 0;
}
if (m[0, i - 1] == 0 && j < N)
{
m[j, i - 1] = 0;
}
}
Print(m);
}
// Clear first row/column if needed
if (!keepFirstRow || !keepFirstColumn)
{
for (int i = 0; i < N; i++)
{
if (!keepFirstRow)
{
m[0, i] = 0;
}
if (!keepFirstColumn)
{
m[i, 0] = 0;
}
}
}
Print(m);
Console.ReadLine();
}
private static void Print(int[,] m)
{
for (int i = 0; i < m.GetLength(0); i++)
{
for (int j = 0; j < m.GetLength(1); j++)
{
Console.Write(" " + m[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}
scheint, wie die folgenden Arbeiten ohne zusätzlichen Platzbedarf:
ersten Hinweis, dass die Elemente der Zeilenzeiten der Elemente der Zeile multipliziert, in dem ein Element ist, um den gewünschten Wert.
Um keinen zusätzlichen Raum zu nutzen (nicht eine neue Matrix zu machen und es auf Füllung, sondern gelten Änderungen an die Matrix direkt), oben links in der Matrix zu starten und die Berechnung für jede ixi Matrix tun (die „beginnt“ bei (0,0)), bevor irgendein Element mit einem Index unter Berücksichtigung> i.
Hoffnung das funktioniert (havent getestet)
Dies ist GETESTET für verschiedene N in C ++, und ist:
ONE PASS , ZWEI bools , NO RECURSION , NO EXTRA MEMORY , gilt für ARBITRARLY LARGE N
(Bisher keine der hier Lösungen alle diese tun.)
Genauer gesagt, ich bin amüsant zwei Schleifenzähler sind in Ordnung. Ich habe zwei const unsigneds, die nur eher existieren als jedes Mal, zur besseren Lesbarkeit berechnet wird. Das Intervall der äußeren Schleife ist [0, N], und der Abstand der inneren Schleife ist [1, n - 1]. Die switch-Anweisung ist in der Schleife meist sehr deutlich zu zeigen, besteht, dass es wirklich nur ein Durchgang ist.
Algorithm Strategie:
Der erste Trick ist uns eine Zeile und eine Spalte aus der Matrix selbst den Inhalt der Matrix zu akkumulieren, diese Speicher alle verfügbar wird durch Offloading uns wirklich von der ersten Zeile und Spalte in zwei booleans wissen müssen. Der zweite Trick ist, zwei Pässe zu bekommen aus einem, unter Verwendung der Symmetrie der Untermatrix und ihre Indizes.
Algorithm Synopsis:
- Scannen Sie die erste Zeile und speichern, wenn sie alle Einsen in einem boolean sind, tun das gleiche für die erste Spalte das Ergebnis in einem zweiten boolean zu speichern.
- Für die Untermatrix mit Ausnahme der ersten Reihe und der ersten Spalte: durchlaufen, von links nach rechts, von oben nach unten, wie man einen Absatz lesen würde. Bei jedem Element besuchen, auch das entsprechende Element besuchen, wenn Besuch die Untermatrix in umgekehrter Reihenfolge besucht werden würde. Für jedes Element besucht und sein Wert in denen, wo seine Reihe kreuzt die erste Spalte, und auch, und sein Wert in dem seine Spalte die erste Zeile kreuzt.
- Sobald das Zentrum der Untermatrix erreicht wird, weiterhin die beiden Elemente gleichzeitig, wie oben zu besuchen. Doch nun die besuchten Elemente Wert an dem UND von wo seine Reihe kreuzt die erste Spalte, und wo seine Spalte kreuzt die erste Reihe. Danach ist die Untermatrix abgeschlossen.
- Mit den beiden booleschen Variablen berechnet am Bitten die erste Reihe und die erste Spalte auf ihre richtigen Werte zu setzen.
Templatized C ++ Implementierung:
template<unsigned n>
void SidewaysAndRowColumn(int((&m)[n])[n]) {
bool fcol = m[0][0] ? true : false;
bool frow = m[0][0] ? true : false;
for (unsigned d = 0; d <= n; ++d) {
for (unsigned i = 1; i < n; ++i) {
switch (d) {
case 0:
frow = frow && m[d][i];
fcol = fcol && m[i][d];
break;
default:
{
unsigned const rd = n - d;
unsigned const ri = n - i;
if (d * n + i < rd * n + ri)
{
m[ d][ 0] &= m[ d][ i];
m[ 0][ d] &= m[ i][ d];
m[ 0][ i] &= m[ d][ i];
m[ i][ 0] &= m[ i][ d];
m[rd][ 0] &= m[rd][ri];
m[ 0][rd] &= m[ri][rd];
m[ 0][ri] &= m[rd][ri];
m[ri][ 0] &= m[ri][rd];
}
else
{
m[ d][ i] = m[ d][0] & m[0][ i];
m[rd][ri] = m[rd][0] & m[0][ri];
}
break;
}
case n:
if (!frow)
m[0][i] = 0;
if (!fcol)
m[i][0] = 0;
};
}
}
m[0][0] = (frow && fcol) ? 1 : 0;
}
Ok, ich merke, dass es nicht ganz ein Spiel ist, aber ich habe es in einem Durchgang ein Bool und ein Byte anstelle von zwei bools mit ... schließen. Ich würde auch nicht für die Effizienz der es bürgen, aber diese Art von Fragen erfordern oft suboptimale Lösungen.
private static void doIt(byte[,] matrix)
{
byte zeroCols = 0;
bool zeroRow = false;
for (int row = 0; row <= matrix.GetUpperBound(0); row++)
{
zeroRow = false;
for (int col = 0; col <= matrix.GetUpperBound(1); col++)
{
if (matrix[row, col] == 0)
{
zeroRow = true;
zeroCols |= (byte)(Math.Pow(2, col));
// reset this column in previous rows
for (int innerRow = 0; innerRow < row; innerRow++)
{
matrix[innerRow, col] = 0;
}
// reset the previous columns in this row
for (int innerCol = 0; innerCol < col; innerCol++)
{
matrix[row, innerCol] = 0;
}
}
else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0)
{
matrix[row, col] = 0;
}
// Force the row to zero
if (zeroRow) { matrix[row, col] = 0; }
}
}
}
Sie können es sorta einen Pass in - wenn Sie zählen nicht die Matrix in Random-Access, um den Zugriff, das die Vorteile, es zu tun Single-Pass an erster Stelle (Cache-Kohärenz / Speicher-Bandbreite beseitigt ).
[edit: einfach, aber falsche Lösung gelöscht]
Sie sollten eine bessere Leistung als jedes Single-Pass-Verfahren erhalten, indem es in zwei Durchgängen zu tun: eine Zeile / Spalte Informationen zu sammeln, und man sich anzuwenden. Das Array (in Zeilenhauptordnung) kohärent zugegriffen wird; für Arrays die Cache-Größe (aber der Zeilen im Cache passen) überschreiten, Daten sollten zweimal und gespeichert einmal aus dem Speicher gelesen werden:
void fixmatrix2(int M[][], int rows, int cols) {
bool clearZeroRow= false;
bool clearZeroCol= false;
for(int j=0; j < cols; ++j) {
if( ! M[0][j] ) {
clearZeroRow= true;
}
}
for(int i=1; i < rows; ++i) { // scan/accumulate pass
if( ! M[i][0] ) {
clearZeroCol= true;
}
for(int j=1; j < cols; ++j) {
if( ! M[i][j] ) {
M[0][j]= 0;
M[i][0]= 0;
}
}
}
for(int i=1; i < rows; ++i) { // update pass
if( M[i][0] ) {
for(int j=0; j < cols; ++j) {
if( ! M[j][0] ) {
M[i][j]= 0;
}
}
} else {
for(int j=0; j < cols; ++j) {
M[i][j]= 0;
}
}
if(clearZeroCol) {
M[i][0]= 0;
}
}
if(clearZeroRow) {
for(int j=0; j < cols; ++j) {
M[0][j]= 0;
}
}
}
Die einfachste Lösung, die ich denken kann unten eingefügt. Die Logik ist, auf die Zeile und Spalte auf Null gesetzt, während das Iterieren aufzuzeichnen.
import java.util.HashSet;
import java.util.Set;
public class MatrixExamples {
public static void zeroOut(int[][] myArray) {
Set<Integer> rowsToZero = new HashSet<>();
Set<Integer> columnsToZero = new HashSet<>();
for (int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray.length; j++) {
if (myArray[i][j] == 0) {
rowsToZero.add(i);
columnsToZero.add(j);
}
}
}
for (int i : rowsToZero) {
for (int j = 0; j < myArray.length; j++) {
myArray[i][j] = 0;
}
}
for (int i : columnsToZero) {
for (int j = 0; j < myArray.length; j++) {
myArray[j][i] = 0;
}
}
for (int i = 0; i < myArray.length; i++) { // record which rows and // columns will be zeroed
for (int j = 0; j < myArray.length; j++) {
System.out.print(myArray[i][j] + ",");
if(j == myArray.length-1)
System.out.println();
}
}
}
public static void main(String[] args) {
int[][] a = { { 1, 0, 1, 1, 0 }, { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 1 } };
zeroOut(a);
}
}
Hier ist meine Ruby-Implementierung mit der die Prüfung einbezogen, Dies würde O (MN) Raum. Wenn wir eine Echtzeit-Aktualisierung möchten (wie die Ergebnisse zeigen, wenn wir Nullen anstatt zu warten, die erste Schleife des Findens Nullen finden) können wir nur eine andere Klasse Variable wie @output erstellen und wenn wir eine Null finden wir @output aktualisieren und nicht @input.
require "spec_helper"
class Matrix
def initialize(input)
@input = input
@zeros = []
end
def solve
@input.each_with_index do |row, i|
row.each_with_index do |element, j|
@zeros << [i,j] if element == 0
end
end
@zeros.each do |x,y|
set_h_zero(x)
set_v_zero(y)
end
@input
end
private
def set_h_zero(row)
@input[row].map!{0}
end
def set_v_zero(col)
@input.size.times do |r|
@input[r][col] = 0
end
end
end
describe "Matrix" do
it "Should set the row and column of Zero to Zeros" do
input = [[1, 3, 4, 9, 0],
[0, 3, 5, 0, 8],
[1, 9, 6, 1, 9],
[8, 3, 2, 0, 3]]
expected = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 9, 6, 0, 0],
[0, 0, 0, 0, 0]]
matrix = Matrix.new(input)
expect(matrix.solve).to eq(expected)
end
end
Der folgende Code erstellt eine Matrix der Größe m, n. Zuerst entscheidet die Dimensionen der Matrix. Ich wollte die Matrix [m] [n] mit dem Zufallsprinzip mit Zahlen zwischen 0..10 füllen. Dann erstellen andere Matrix mit den gleichen Abmessungen und füllt ihn mit -1S (Endmatrix). Dann durchlaufen die anfängliche Matrix zu sehen, ob Sie 0. treffen wird, wenn Sie vor Ort getroffen (x, y), geht auf die endgültige Matrix und füllen Sie die Zeile x mit 0 s und Spalte y mit 0 s. Am Ende gelesen durch die letzte Matrix, wenn der Wert -1 (Originalwert), um den Wert an der gleichen Stelle der ursprünglichen Matrix bis zum endgültigen kopieren.
public static void main(String[] args) {
int m = 5;
int n = 4;
int[][] matrixInitial = initMatrix(m, n); // 5x4 matrix init randomly
int[][] matrixFinal = matrixNull(matrixInitial, m, n);
for (int i = 0; i < m; i++) {
System.out.println(Arrays.toString(matrixFinal[i]));
}
}
public static int[][] matrixNull(int[][] matrixInitial, int m, int n) {
int[][] matrixFinal = initFinal(m, n); // create a matrix with mxn and init it with all -1
for (int i = 0; i < m; i++) { // iterate in initial matrix
for (int j = 0; j < n; j++) {
if(matrixInitial[i][j] == 0){ // if a value is 0 make rows and columns 0
makeZeroX(matrixFinal, i, j, m, n);
}
}
}
for (int i = 0; i < m; i++) { // if value is -1 (original) copy from initial
for (int j = 0; j < n; j++) {
if(matrixFinal[i][j] == -1) {
matrixFinal[i][j] = matrixInitial[i][j];
}
}
}
return matrixFinal;
}
private static void makeZeroX(int[][] matrixFinal, int x, int y, int m, int n) {
for (int j = 0; j < n; j++) { // make all row 0
matrixFinal[x][j] = 0;
}
for(int i = 0; i < m; i++) { // make all column 0
matrixFinal[i][y] = 0;
}
}
private static int[][] initMatrix(int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Random rn = new Random();
int random = rn.nextInt(10);
matrix[i][j] = random;
}
}
for (int i = 0; i < m; i++) {
System.out.println(Arrays.toString(matrix[i]));
}
System.out.println("******");
return matrix;
}
private static int[][] initFinal(int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = -1;
}
}
return matrix;
}
// another approach
/**
* @param matrixInitial
* @param m
* @param n
* @return
*/
private static int[][] matrixNullNew(int[][] matrixInitial, int m, int n) {
List<Integer> zeroRowList = new ArrayList<>(); // Store rows with 0
List<Integer> zeroColumnList = new ArrayList<>(); // Store columns with 0
for (int i = 0; i < m; i++) { // read through the matrix when you hit 0 add the column to zeroColumnList and add
// the row to zeroRowList
for (int j = 0; j < n; j++) {
if (matrixInitial[i][j] == 0) {
if (!zeroRowList.contains(i)) {
zeroRowList.add(i);
}
if (!zeroColumnList.contains(j)) {
zeroColumnList.add(j);
}
}
}
}
for (int a = 0; a < m; a++) {
if (zeroRowList.contains(a)) { // if the row has 0
for (int b = 0; b < n; b++) {
matrixInitial[a][b] = 0; // replace all row with zero
}
}
}
for (int b = 0; b < n; b++) {
if (zeroColumnList.contains(b)) { // if the column has 0
for (int a = 0; a < m; a++) {
matrixInitial[a][b] = 0; // replace all column with zero
}
}
}
return matrixInitial;
}
Hier ist meine Lösung. Wie Sie aus dem Code, da eine M * N Matrix sehen können, setzt er die gesamte Zeile auf Null, sobald es ein Null in dieser row.the Zeitkomplexität meiner Lösung prüft O (M * N). Ich teile die ganze Klasse, die eine statische besiedelte Array zum Testen hat und ein Display-Array-Verfahren das Ergebnis in der Konsole zu sehen.
public class EntireRowSetToZero {
static int arr[][] = new int[3][4];
static {
arr[0][0] = 1;
arr[0][1] = 9;
arr[0][2] = 2;
arr[0][3] = 2;
arr[1][0] = 1;
arr[1][1] = 5;
arr[1][2] = 88;
arr[1][3] = 7;
arr[2][0] = 0;
arr[2][1] = 8;
arr[2][2] = 4;
arr[2][3] = 4;
}
public static void main(String[] args) {
displayArr(EntireRowSetToZero.arr, 3, 4);
setRowToZero(EntireRowSetToZero.arr);
System.out.println("--------------");
displayArr(EntireRowSetToZero.arr, 3, 4);
}
static int[][] setRowToZero(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if(arr[i][j]==0){
arr[i]=new int[arr[i].length];
}
}
}
return arr;
}
static void displayArr(int[][] arr, int n, int k) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println("");
}
}
}
One Pass -. Ich habe die Eingabe nur einmal durchlaufen, sondern verwenden ein neues Array und nur zwei zusätzliche Boolesche Variablen
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
boolean rowDel = false, colDel = false;
int arr[][] = new int[n][n];
int res[][] = new int[n][n];
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
res[i][j] = arr[i][j];
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (arr[i][j] == 0)
colDel = rowDel = true; //See if we have to delete the
//current row and column
if (rowDel == true){
res[i] = new int[n];
rowDel = false;
}
if(colDel == true){
for (int k = 0; k < n; k++) {
res[k][j] = 0;
}
colDel = false;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
sc.close();
}
