Setzen Sie jede Zelle in der Matrix auf 0, wenn diese Zeile oder Spalte eine 0 enthält

152

Gegeben eine NxN-Matrix mit 0s und 1s. Setzen Sie jede Zeile, die a 0auf alle 0s enthält , und jede Spalte, die a 0auf alle 0s enthält.

Beispielsweise

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

führt zu

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 boolesche Variablen und einen Durchgang umfasst. Deshalb suche ich nach dieser Antwort.

Übrigens, stellen Sie sich vor, es ist eine Bitmatrix, daher dürfen nur 1s und 0s in der Matrix sein.

Jaircazarin-altes Konto
quelle
1
Huh? Was ist "wann immer Sie begegnen"? In welcher Reihenfolge begegnen Sie den Elementen in der Matrix? Und wenn Sie auf alle Bits stoßen, bekommen Sie dann nicht trotzdem alle Nullen?
ShreevatsaR
Nun, die Reihenfolge, in der Sie sich entscheiden, den Elementen zu begegnen, ist Ihre Entscheidung. Die Sache ist, dass Sie nur die richtigen Elemente auf 0 setzen müssen. Wenn Sie auf alle auf 0 gesetzten Bits stoßen, wird die Matrix immer noch mit Nullen gefüllt.
Jaircazarin-altes Konto
Was sind "die richtigen Elemente"? Erhalten Sie zwei Matrizen, eine "Quell" -Matrix und eine "Ziel" -Matrix, und Sie müssen entscheiden, in welcher Reihenfolge Sie auf die Elemente "treffen", um die "Ziel" -Matrix zu erhalten?
ShreevatsaR
1
Ich denke, Sie haben etwas für den 1-Pass-Gedanken falsch gehört. Es kann linear in 2 Durchgängen durchgeführt werden, ohne zusätzlichen Speicher, nur 2 Boolesche Werte ;-) Ich gehe also stark davon aus, dass es die Lösung ist, die er meinte (siehe unten)
Piotr Lesnicki
1
Können Sie bitte mit Ihrem Freund überprüfen, ob die Problembeschreibung tatsächlich korrekt ist? Ich dachte, ich könnte dies mit Hamming-Codes oder Paritätsbits tun, aber bisher hatte ich keinen Erfolg, und das Problem bleibt in meinem Kopf hängen. :)
CSL

Antworten:

96

Ok, ich bin müde, da es hier 3 Uhr morgens ist, aber ich habe einen ersten Versuch mit genau 2 Durchgängen für jede Zahl in der Matrix, also in O (NxN) und es ist linear in der Größe der Matrix.

Ich benutze die erste Spalte und die erste Zeile als Markierungen, um zu wissen, wo Zeilen / Spalten mit nur Einsen sind. Dann gibt es 2 Variablen l und c, an die man sich erinnern muss, wenn die erste Zeile / Spalte auch alle Einsen sind. Der erste Durchgang setzt also die Markierungen und setzt den Rest auf Null zurück.

Der zweite Durchgang setzt 1 an Stellen, an denen Zeilen und Spalten als 1 markiert wurden, und setzt die erste Zeile / Spalte in Abhängigkeit von l und c zurück.

Ich bezweifle stark, dass ich in einem Durchgang fertig sein kann, da Quadrate am Anfang von Quadraten am Ende abhängen. Vielleicht kann mein 2. Durchgang 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)
Piotr Lesnicki
quelle
Ein Problem hierbei ist, wenn n> sizeof (c), dann bricht es zusammen. Um dies zu erweitern, um im allgemeinen Fall von n zu funktionieren, müssten Sie Ihr Bitfeld dynamisch dimensionieren, was meiner Meinung nach die durch das Problem gegebene Einschränkung verletzen würde.
Adam
Nein, c ist kein Bitfeld, es ist nur ein Trottel. Das & = ist keine bitweise Operation (nun ja, aber auf einem 1-Bit-Wert), es ist da, weil c Ihnen sagt, ob die erste Spalte alle 1 (wahr) ist oder eine 0 (falsch) enthält.
Steve Jessop
2
Es schlägt fehl, wenn die oberste Zeile [0,1,1,1 ...] ist. Meine Fehlerbehebung besteht darin, l auf m [0] [0] anstatt auf 1 zu initialisieren
paperhorse
in der Tat sollte l = 1 für i im Bereich (1, N): l & = m [0] [i] sollte l = 1 für i im Bereich (N) sein: l & = m [0] [i]
Kristof Neirynck
1
Übrigens glaube ich, dass die Bedingung im zweiten Durchgang ungefähr so ​​sein sollte: wenn m [i] [0] | m [0] [j]:
Jaircazarin-altes Konto
16

Dies kann nicht in einem Durchgang erfolgen, da sich ein einzelnes Bit in beliebiger Reihenfolge auf die Bits davor und danach auswirkt. IOW Unabhängig von der Reihenfolge, in der Sie das Array durchlaufen, können Sie später auf eine 0 stoßen, was bedeutet, dass Sie zurückgehen und eine vorherige 1 in eine 0 ändern müssen.

Aktualisieren

Die Leute scheinen zu glauben, dass man dies durch einen einzigen Durchgang lösen kann, indem man N auf einen festen Wert (z. B. 8) beschränkt. Nun, das ist a) der Punkt fehlt und b) nicht die ursprüngliche Frage. Ich würde keine Frage zum Sortieren posten und eine Antwort erwarten, die anfing "vorausgesetzt, Sie möchten nur 8 Dinge sortieren ...".

Das heißt, es ist ein vernünftiger Ansatz, wenn Sie wissen, dass N tatsächlich auf 8 beschränkt ist. Meine Antwort oben beantwortet die ursprüngliche Frage, die keine solche Einschränkung aufweist.

Draemon
quelle
Es kann nicht in einem Durchgang ohne zusätzlichen Speicher durchgeführt werden. Dies kann in einem Durchgang durchgeführt werden, wenn eine andere NxN-Matrix zum Speichern der Ergebnisse vorhanden ist. Ebenso kann es mit einigen Bit-Twiddles und zwei Durchgängen ohne zusätzlichen Speicher durchgeführt werden.
paxos1977
2
Sie können es immer noch nicht in einem Durchgang tun, selbst wenn Sie eine temporäre Matrix verwenden, oder es gibt etwas Seltsames, das ich hier nicht bekomme. Sie benötigen einen Durchgang, um die Zeilen- / Spalteninformationen abzuleiten, und einen, um alles festzulegen.
Lasse V. Karlsen
Ich habe dieses Problem gelöst, indem ich erkannt habe, dass nur ein eindeutiger Wert ungleich Null pro Zeile möglich ist, und ihn nur als Referenz zugewiesen habe.
Daniel Papasian
@ceretullis, lassevk: Ich denke immer noch, dass es nicht in einem Durchgang gemacht werden kann. Übergänge über diese zweite Matrix müssten zählen - andernfalls könnten Sie die Matrix einfach in einem Durchgang kopieren und mit der Kopie arbeiten, wie Sie möchten. @ Daniel Papasian: Ihre Lösung skaliert nicht, wo N> #bits in int / long / Whatever
Draemon
Draemon, die Technik lässt sich gut skalieren, es ist nur Mathematik - Sie können entweder Hardware erstellen, die dies tut, oder Sie können Softwaretechniken verwenden, um Zahlen zu manipulieren, die größer als Ihre Wortgröße sind. Keiner von beiden verstößt gegen die Einschränkungen des Problems, IMHO
Daniel Papasian
10

Meine Idee ist es also, die Werte in der letzten Zeile / Spalte als Flag zu verwenden, um anzuzeigen, ob alle Werte in der entsprechenden Spalte / Zeile 1s sind.

Verwenden eines Zick-Zack-Scans durch die gesamte Matrix mit Ausnahme der letzten Zeile / Spalte. Bei jedem Element setzen Sie den Wert in der letzten Zeile / Spalte auf das logische UND von sich selbst mit dem Wert im aktuellen Element. Mit anderen Worten, wenn Sie eine 0 drücken, wird die letzte Zeile / Spalte auf 0 gesetzt. Wenn Sie eine 1 wählen, ist der Wert in der letzten Zeile / Spalte nur dann 1, wenn er bereits 1 war. Setzen Sie in jedem Fall das aktuelle Element auf 0.

Wenn Sie fertig sind, sollte Ihre letzte Zeile / Spalte 1s haben, wenn die entsprechende Spalte / Zeile mit 1s gefüllt wurde.

Führen Sie einen linearen Scan durch die letzte Zeile und Spalte durch und suchen Sie nach 1s. Setzen Sie 1s in die entsprechenden Elemente im Hauptteil der Matrix, wobei die letzte Zeile und Spalte beide 1s sind.

Das Codieren ist schwierig, um Fehler usw. zu vermeiden, aber es sollte in einem Durchgang funktionieren.

Alastair
quelle
Sehr schön ... Ich habe in den gleichen Zeilen nachgedacht, aber die letzte Zeile / Spalte nicht zum Speichern dieser Informationen verwendet, sodass ich keinen zusätzlichen Speicher für ein Paar Nx1-Arrays hatte.
Dave Sherohman
1
Das sieht für mich nach zwei Durchgängen aus - ein Durchgang ist der Zick-Zack-Scan, der zweite ist der "Satz 1s in den entsprechenden Elementen im Hauptteil der Matrix, wobei die letzte Zeile und Spalte beide 1s sind".
Adam Rosenfield
Der Zick-Zack-Scan (der, wie mir jemand sagte, nicht unbedingt erforderlich ist) durchläuft alle ABER die letzte Zeile / Spalte. Das Scannen der letzten / Zeilenspalte dupliziert also keine zuvor gescannten Elemente. Daher ein Durchgang. Mit anderen Worten ist es O (N ^ 2) für eine N * N-Matrix.
Alastair
6

Ich habe hier eine Lösung, die in einem einzigen Durchgang ausgeführt wird und die gesamte Verarbeitung "an Ort und Stelle" ohne zusätzlichen Speicher ausführt (außer zum Erweitern des Stapels).

Es verwendet Rekursion, um das Schreiben von Nullen zu verzögern, was natürlich die Matrix für die anderen Zeilen und Spalten zerstören würde:

#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();
}
Adam
quelle
2
Gute Lösung, aber Sie verwenden technisch gesehen mehr Speicher als die beiden zulässigen Booleschen Werte (obwohl auf dem Stapel).
CSL
1
Dies ist> 1 Durchgang. Wenn Sie (rowIndex, i) und (i, colIndex) drucken, während auf sie in checkRow und checkCol zugegriffen wird, sehen Sie, dass auf jedes Element mehrmals zugegriffen wird.
Draemon
Draemon: Sie haben Recht, ich denke, wir brauchen eine klare Definition von "Single Pass" vom Rätselmacher. Wenn er tatsächlich meint, dass auf jedes Element nur einmal zugegriffen werden kann, brauchen wir eine andere Lösung.
Adam
Ich stelle mir vor, dass das ursprüngliche Problem (das uns über das Telefonspiel gekommen ist) bedeutete, dass das Problem "an Ort und Stelle" gelöst werden sollte, was bedeutet, dass Sie keine weitere Kopie der Matrix haben. Und optimalere Lösungen benötigen nicht einmal temporären swap () wie Speicher für die Verarbeitung.
Adam
Ich bezweifle auch, dass sich die Einschränkungen auf den resultierenden Maschinencode beziehen. Das heißt, der von mir bereitgestellte "Code" verwendet nur 2 Bools. Abhängig davon, welche Optimierungen mein Compiler vornimmt, könnte das ganze verdammte Ding inline sein oder wer weiß was noch. Ich denke meine Lösung ist richtig;)
Adam
4

Ich denke nicht, dass es machbar ist. Wenn Sie sich auf dem ersten Quadrat befinden und dessen Wert 1 ist, können Sie die Werte der anderen Quadrate in derselben Zeile und Spalte nicht ermitteln. Sie müssen diese also überprüfen. Wenn es eine Null gibt, kehren Sie zum ersten Quadrat zurück und ändern Sie den Wert in Null. Ich empfehle, dies in zwei Durchgängen zu tun - im ersten Durchgang werden Informationen darüber gesammelt, welche Zeilen und Spalten auf Null gesetzt werden müssen (die Informationen werden in einem Array gespeichert, sodass wir zusätzlichen Speicher verwenden). Der zweite Durchgang ändert die Werte. Ich weiß, dass dies nicht die Lösung ist, nach der Sie suchen, aber ich denke, es ist eine praktische. Die von Ihnen angegebenen Einschränkungen machen das Problem unlösbar.

Boyan
quelle
Ich habe fast die gleiche Lösung (siehe unten) ohne zusätzliche Arrays. und es ist lineare Zeit (aber 2 Pässe obwohl)
Piotr Lesnicki
@Piotr: Ja, der zweite Durchgang scheint unvermeidlich. Die Einführung von Arrays zum Speichern der von mir vorgeschlagenen Zeilen- und Spalteninformationen macht den Algorithmus einfacher und etwas schneller, da weniger Überprüfungen und Wertänderungen erforderlich sind. Es ist ein Kompromiss zwischen Speicher und Effizienz.
Boyan
3

Ich kann es mit zwei ganzzahligen Variablen und zwei Durchgängen machen (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));
Finsternis
quelle
Ist das C #? Was bedeutet das ~?
Sker
Es ist C ++. ~invertiert alle Bits in einer Variablen. Aus 0x00000000 wird 0x00000000. Ich beginne im Grunde mit allen und lösche das Bit für eine Zeile / Spalte, wenn ich eine 0 finde. CompleteCols hat die Bits 2 und 3 gesetzt und CompleteRows hat die Bits 2 und 4 gesetzt (0 basierend).
Eclipse
Dann setzen Sie einfach die Bits in der Matrix, die einer Eins in CompleteCols und CompleteRows entsprechen.
Eclipse
3

Das Problem kann in einem Durchgang gelöst werden

Speichern der 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 drucken Sie alle Werte als 0 für die in a und b gespeicherten Werte von i und j. Die restlichen Werte sind 1, dh (3,3) (3,4) (5,3) und (5,4).

Siddharth
quelle
1

Eine andere Lösung, die zwei Durchgänge benötigt, besteht darin, UNDs 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 könnte einen solchen Algorithmus unter Verwendung von Paritätsbits , Hamming-Codes oder dynamischer Programmierung entwerfen, möglicherweise unter Verwendung dieser beiden Booleschen Werte als 2-Bit-Zahl, aber ich hatte noch keinen Erfolg.

Können Sie bitte die Problemstellung mit Ihrem Techniker überprüfen und uns Bescheid geben? Wenn es ist in der Tat eine Lösung, möchte ich auf das Problem halten kratzen.

csl
quelle
1

Behalten Sie eine einzelne Variable bei, um zu verfolgen, was alle Zeilen UND-verknüpft sind.

Wenn eine Zeile -1 (alle 1s) ist, machen Sie die nächste Zeile zu einem Verweis auf diese Variable

Wenn eine Zeile alles andere als eine 0 ist, können Sie alles in einem Durchgang ausführen. Pseudocode:

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 in einem einzigen Durchgang tun - aber hier wird davon ausgegangen, dass N klein genug ist, damit die CPU in einer einzelnen Zeile rechnen kann. Andernfalls müssen Sie jede Zeile durchlaufen, um festzustellen, ob alles vorhanden ist 1s oder nicht, glaube ich. Aber wenn Sie nach Algen fragen und meine Hardware nicht einschränken, würde ich meine Antwort einfach mit "Erstellen Sie eine CPU, die N-Bit-Arithmetik unterstützt ..." beginnen.

Hier ist ein Beispiel, wie es in C gemacht werden kann. Hinweis Ich argumentiere, dass Werte und arr zusammen das Array darstellen und p und numproduct meine Iterator- und AND-Produktvariablen sind, die zur Implementierung des Problems verwendet werden. (Ich hätte arr mit Zeigerarithmetik durchlaufen können, um 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, was das Ergebnis für die gegebenen Eingaben ist.

Oder in PHP, wenn die Leute denken, dass meine Stack-Spiele in C betrügen (ich schlage Ihnen vor, dass dies nicht der Fall ist, weil ich die Matrix nach Belieben speichern kann):

<?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);

Vermisse ich etwas

Daniel Papasian
quelle
Dies funktioniert nicht, wenn N größer ist als die Anzahl der Bits in einem int / long / was auch immer, also denke ich nicht, dass es zählt.
Draemon
Es werden auch keine Dinge abgefangen, wenn sich die Nullen am unteren Rand des Arrays befinden (versuchen Sie es mit den Werten [] = {-1, -9, -1, 14, -10}).
Eclipse
Draemon, ich gebe in meiner Antwort an, dass Sie ohne Hardwareeinschränkungen als Teil der Frage mit "Erstellen Sie eine CPU, die N-Bit-Arithmetik unterstützt" beginnen.
Daniel Papasian
Josh, ich folge nicht. Mit der C- oder PHP-Lösung und dem von Ihnen vorgeschlagenen Array erhalte ich 6 0 6 0 0, was meiner Meinung nach die richtige Antwort ist.
Daniel Papasian
@ Daniel - Das kannst du nicht, weil N keine Konstante ist. Außerdem "ist das Erstellen eines neuen Computers mit 1-Mbit-Wörtern kaum ein vernünftiger algorithmischer Schritt.
Draemon
1

Schöne Herausforderung. Diese Lösung verwendet nur zwei Boolesche Werte, die auf dem Stapel erstellt wurden. Die Booleschen Werte werden jedoch 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;
}

Dies 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

Ändern Sie dann die Werte in diesem Muster bei der Rückkehr für jede der Scanfunktionen. (Prost):

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

eaanon01
quelle
Ich würde vermuten, dass dies nicht korrekt ist, da Sie immer noch viel mehr als zwei Boolesche Werte auf Ihrem Stapel verbrauchen.
CSL
Da bin ich traurig, zwei Boolesche. Dies ist das, was ich den von ihm angegebenen Spezifikationen am nächsten kommen kann. Ich würde gerne eine tatsächliche Lösung hier sehen. Wenn es möglich ist.
eaanon01
Ich glaube nicht, dass sich die Anforderungen auf das Wachstum des Stapels beziehen. Ich denke, das ist eine absolut gültige Lösung.
Adam
Das ist auch mein Gedanke. Aber ich kann nicht sicher sein, bis jemand anderes eine bessere Lösung veröffentlicht. Zumindest ist meine Lösung kompilierbar und kann von jedem überprüft werden. :) ... Ich bin nicht von Psudo-Code für praktische Probleme zu finden. Thnx
eaanon01
1

Okay, das ist eine Lösung, die

  • verwendet nur einen extra langen Wert für den Arbeitsspeicher.
  • verwendet keine Rekursion.
  • ein Durchgang von nur N, nicht einmal N * N.
  • funktioniert für andere Werte von N, benötigt jedoch neue #defines.
#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;
    }
Anthony Lambert
quelle
Es ist eine schöne Lösung, um sicher zu sein. Und ich nehme an, dass jede Lösung hier mindestens eine der Anforderungen vernachlässigt. Eine Lösung mit einem maximal zulässigen Wert für N zu haben, ist also nicht das Schlimmste auf der Welt, also gute Arbeit in diesem Fall :)
Adam,
Die Beschränkung von N auf 8 und die Behauptung, dass dies die One-Pass-Anforderung erfüllt, ist einfach nur dumm. Dies ist keine allgemeine Lösung. In der Frage wurde keine Einschränkung der Größe von N angegeben, sodass Sie nur ein Unterproblem gelöst haben.
Draemon
Aber alle diese Lösungen haben auf die eine oder andere Weise eine Grenze für N.
Anthony Lambert
Zu sagen, dass es ein Durchgang von N ist, ist offensichtlich völlig falsch. Selbst wenn nur der Wert jeder Position in der ursprünglichen Matrix gelesen wird, ist O (N ^ 2), und es ist auf jeden Fall notwendig, den Wert an jeder Position mindestens einmal zu lesen, um die Lösung berechnen zu können. Selbst wenn Sie Werte innerhalb einer langen Länge als einzelne Bits speichern, wird der Zugriff auf jedes Bit O (N ^ 2) sein, da O (N ^ 2) Bits vorhanden sind.
Alderath
Es ist eindeutig ein Durchgang, bei dem der RowGrid-Wert das gesamte Raster speichert und nach dem ersten Lesen eines der Prozessorregister für den gesamten Algorithmus wäre, wenn der Optimierer gut ist.
Anthony Lambert
1

Tatsächlich. Wenn Sie nur den Algorithmus ausführen und die Ergebnisse ausdrucken möchten (dh nicht wiederherstellen möchten, können Sie dies problemlos in einem Durchgang tun. Das Problem tritt auf, wenn Sie versuchen, das Array während der Ausführung des Algorithmus zu ändern.

Hier ist meine Lösung. Es geht lediglich darum, die Zeilen- / Spaltenwerte für das Element eines Giveins (i, j) UND-verknüpft und auszudrucken.

#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;
    }
}
Kenny Cason
quelle
1

Ich habe versucht, dieses Problem in C # zu lösen.

Ich habe zwei Schleifenvariablen (i und j) verwendet, abgesehen von der tatsächlichen Matrix und n, die ihre Dimension darstellen

Die Logik, die ich versucht habe, ist:

  1. Berechnen Sie AND für Zeilen und Spalten, die an jedem konzentrischen Quadrat der Matrix beteiligt sind
  2. Speichern Sie es in seinen Eckzellen (ich habe sie gegen den Uhrzeigersinn gespeichert)
  3. Zwei Bool-Variablen werden verwendet, um Werte von zwei Ecken bei der Auswertung eines bestimmten Quadrats beizubehalten.
  4. Dieser Prozess würde enden, wenn sich die äußere Schleife (i) auf halbem Weg befindet.
  5. Bewerten Sie die Ergebnisse anderer Zellen basierend auf den Eckzellen (für den Rest von i). Überspringen Sie während dieses Vorgangs die Eckzellen.
  6. Wenn ich n erreiche, würden alle Zellen außer den Eckzellen ihr Ergebnis haben.
  7. Aktualisieren Sie die Eckzellen. Dies ist eine zusätzliche Iteration auf die Länge von n / 2, abgesehen von der im Problem erwähnten Einzeldurchlaufbeschränkung.

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;
            }
        }
    }
}
BK
quelle
1

Ein Durchgang - Ich habe die Eingabe nur einmal durchlaufen, aber ein neues Array und nur zwei zusätzliche boolesche Variablen verwendet.

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();

    }
RahulDeep Attri
quelle
0

Angesichts der Einschränkungen ist dies zwar unmöglich, aber die platzsparendste Methode besteht darin, die Matrix in einer überlappenden, abwechselnden Zeilen- / Spaltenform zu durchlaufen, wodurch ein Muster entsteht, das dem Verlegen von Ziegeln im Zick-Zack ähnelt:

-----
|----
||---
|||--
||||-

Wenn Sie dies verwenden, gehen Sie wie angegeben in jede Zeile / Spalte. Wenn Sie zu irgendeinem Zeitpunkt auf eine 0 stoßen, legen Sie eine boolesche Variable fest und gehen Sie diese Zeile / Spalte erneut durch, wobei Sie die Einträge auf 0 setzen.

Dies erfordert keinen zusätzlichen Speicher und verwendet nur eine boolesche Variable. Wenn die "ferne" Kante auf 0 gesetzt ist, ist dies leider der schlimmste Fall, und Sie durchlaufen das gesamte Array zweimal.

cdeszaq
quelle
Ich könnte mich irren, aber sind Sie sicher, dass dies funktioniert? Wenn Sie beispielsweise die dritte Spalte ausführen, woher wissen Sie, ob der Wert oben in der ersten Zeile eine 1 oder eine 0 war, bevor Sie die erste Zeile verarbeitet haben?
Steve Jessop
Sie wissen es nicht, müssen es aber auch nicht. Wenn es eine 0 war, muss die gesamte Spalte 0 sein. Wenn der Wert in der vorherigen Zeile 1 ist, wissen Sie, dass alle Zeilen darüber 1 sind (und immer waren).
Dave Sherohman
0

Erstellen Sie eine Ergebnismatrix und setzen Sie alle Werte auf 1. Gehen Sie die Datenmatrix durch, sobald eine 0 auftritt, und setzen Sie die Spalte der Ergebnismatrixzeile auf 0

Am Ende des ersten Durchgangs hat die Ergebnismatrix die richtige Antwort.

Sieht ziemlich einfach aus. Gibt es einen Trick, den ich vermisse? Dürfen Sie keine Ergebnismenge verwenden?

BEARBEITEN:

Sieht aus wie eine F # -Funktion, aber das ist ein bisschen betrügerisch, da die Funktion rekursiv sein kann, obwohl Sie einen einzelnen Durchgang ausführen.

Es sieht so aus, als würde der Interviewer herausfinden, ob Sie mit funktionaler Programmierung vertraut sind.

mson
quelle
1
Die Verwendung einer Ergebnismenge würde zusätzlichen Speicherplatz beanspruchen.
Cdeszaq
Die funktionale Programmierung würde das ursprüngliche Array nicht verändern.
Svante
0

Nun, ich habe eine In-Place-Lösung mit einem Durchgang (nicht rekursiv) mit 4 Bools und 2 Schleifenzählern entwickelt. Ich habe es nicht geschafft, es auf 2 Bools und 2 Ints zu reduzieren, aber ich wäre nicht überrascht, wenn es möglich wäre. Es werden ungefähr 3 Lese- und 3 Schreibvorgänge für jede Zelle ausgeführt, und es sollte O (N ^ 2) sein, d. H. linear in der Arraygröße.

Ich habe ein paar Stunden gebraucht, um dieses Problem zu lösen - ich möchte nicht unter dem Druck eines Interviews darauf kommen müssen! Wenn ich einen Booboo gemacht habe, bin ich zu müde, um ihn zu erkennen ...

Ähm ... Ich definiere "Single-Pass" als einen Durchlauf durch die Matrix, 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;
}

quelle
0

Ich hoffe, Ihnen gefällt meine 1-Pass-C # -Lösung

Sie können ein Element mit O (1) abrufen und benötigen nur den Platz einer Zeile und einer 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
*/
Nick
quelle
Ich denke, das einzige Problem könnte sein, dass Sie zwei zusätzliche Datenfelder verwenden, damit dies funktioniert. Eine der Bedingungen ist, keinen zusätzlichen Speicher zu verwenden. Aber schön! Dies ist im Grunde, was ich in meiner Antwort getan habe :)
Kenny Cason
0

1 Durchgang, 2 Boolesche Werte. Ich muss nur annehmen, dass die Ganzzahlindizes in den Iterationen nicht zählen.

Dies ist keine vollständige Lösung, aber ich kann diesen Punkt nicht bestehen.

Wenn ich nur feststellen könnte, ob eine 0 eine ursprüngliche 0 oder eine 1 ist, die in eine 0 konvertiert wurde, müsste ich keine -1 verwenden, und das würde funktionieren.

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 besteht darin, anhand der ersten Hälfte der Prüfung einer Zeile oder Spalte festzustellen, ob sie eine 0 enthält, und anhand der letzten Hälfte, um die Werte festzulegen. Dazu werden x und width-x sowie dann y und height betrachtet -y in jeder Iteration. Basierend auf den Ergebnissen der ersten Hälfte der Iteration verwende ich die letzte Hälfte der Iteration, um die Einsen in -1 zu ändern, wenn eine 0 in der Zeile oder Spalte gefunden wurde.

Ich habe gerade festgestellt, dass dies mit nur 1 Booleschen Wert möglich ist und 1 bis ... übrig bleibt.

Ich poste dies in der Hoffnung, dass jemand sagen könnte: "Ah, mach das einfach ..." (Und ich habe viel zu viel Zeit damit verbracht, es nicht zu posten.)

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
rvarcher
quelle
0

Niemand benutzt binäre Formen? da es nur 1 und 0 ist. Wir können binäre Vektoren verwenden.

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
KFL
quelle
0

Sie können so etwas tun, um einen Durchgang, aber eine Eingabe- und Ausgabematrix zu verwenden:

output(x,y) = col(xy) & row(xy) == 2^n

wo col(xy)ist das Bits in der Spalte , die den Punkt enthält xy; row(xy)sind die Bits in der Zeile, die den Punkt enthalten xy. nist die Größe der Matrix.

Dann einfach den Eingang durchlaufen. Möglicherweise erweiterbar, um platzsparender zu sein?

Warbum
quelle
0

Ein Matrix-Scan, zwei Boolesche Werte, keine Rekursion.

Wie vermeide ich den zweiten Durchgang? Der zweite Durchgang wird benötigt, um die Zeilen oder Spalten zu löschen, wenn die Null am Ende erscheint.

Dieses Problem kann jedoch gelöst werden, da wir beim Scannen der Zeile #i bereits den Zeilenstatus für die Zeile # i-1 kennen. Während wir also die Zeile #i scannen, können wir gleichzeitig die Zeile # i-1 löschen, wenn dies erforderlich ist.

Die gleiche Lösung funktioniert für Spalten, aber wir müssen Zeilen und Spalten gleichzeitig scannen, während die Daten bei der nächsten Iteration nicht geändert werden.

Zum Speichern des Status der ersten Zeile und der ersten Spalte sind zwei Boolesche Werte erforderlich, da ihre Werte während der Ausführung des Hauptteils des Algorithmus geändert werden.

Um das Hinzufügen weiterer Boolescher Werte zu vermeiden, speichern wir das "clear" -Flag für die Zeilen und Spalten in der ersten Zeile und Spalte der Matrix.

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();
}
Artemix
quelle
0

Folgendes scheint ohne zusätzlichen Platzbedarf zu funktionieren:

Beachten Sie zunächst, dass das Multiplizieren der Elemente der Zeile mit den Elementen der Zeile, in der sich ein Element befindet, den gewünschten Wert ergibt.

Um keinen zusätzlichen Speicherplatz zu verwenden (keine neue Matrix erstellen und auffüllen, sondern Änderungen direkt auf die Matrix anwenden), beginnen Sie oben links in der Matrix und führen Sie die Berechnung für eine ixi-Matrix durch (die bei (0 "" beginnt ") , 0)) bevor ein Element mit einem Index> i betrachtet wird.

hoffe das funktioniert (havent testet)

DFF
quelle
Scheint falsch zu sein. Angenommen, Zeile 0 hat nur 1 Werte. Wenn der endgültige Wert, den Sie für (0,0) festgelegt haben, 0 ist, setzen Sie später die gesamte Zeile auf 0, was nicht unbedingt korrekt ist. Sie müssen tatsächlich 2 Werte pro Zelle speichern, um einen dynamischen Programmierstil nach Ihrem Prinzip zu erstellen.
Eyal Schneider
Sicher, du hast recht. Anstatt zwei Werte zu speichern, könnte ich auch eine dritte Möglichkeit verwenden, z. B. -1, die für Zellen steht, die 1 in der "alten" Matrix sind und schließlich durch eine 0 ersetzt werden. Natürlich muss man auf diese Weise absolut nehmen Werte nach Multiplikationen. Am Ende werden alle -1 durch Nullen ersetzt.
DFF
0

Dies ist für verschiedene N in C ++ getestet und ist:
EIN PASS , ZWEI BOOLS , KEINE REKURSION , KEIN ZUSÄTZLICHER SPEICHER , HÄLT FÜR ARBITRAR GROSSES N.
(Bisher macht keine der Lösungen hier ALLE diese.)

Genauer gesagt, ich amüsiere mich, dass zwei Schleifenzähler in Ordnung sind. Ich habe zwei nicht signierte Konstanten, die nur existieren und nicht jedes Mal zur besseren Lesbarkeit berechnet werden. Das Intervall der äußeren Schleife ist [0, N] und das Intervall der inneren Schleife ist [1, n - 1]. Die switch-Anweisung ist in der Schleife meistens vorhanden, um sehr deutlich zu zeigen, dass es sich wirklich nur um einen Durchgang handelt.

Algorithmusstrategie:

Der erste Trick besteht darin, eine Zeile und eine Spalte aus der Matrix selbst zu erstellen, um den Inhalt der Matrix zu akkumulieren. Dieser Speicher wird verfügbar, indem alles, was wir wirklich wissen müssen, aus der ersten Zeile und Spalte in zwei Boolesche Werte verschoben wird. Der zweite Trick besteht darin, zwei Durchgänge aus einem herauszuholen, indem die Symmetrie der Submatrix und ihrer Indizes verwendet wird.

Algorithmus Synopsis:

  • Scannen Sie die erste Zeile und speichern Sie, wenn alle in einem Booleschen Wert sind. Machen Sie dasselbe für die erste Spalte, in der das Ergebnis in einem zweiten Booleschen Wert gespeichert wird.
  • Für die Untermatrix ohne die erste Zeile und die erste Spalte: Iterieren Sie durch, von links nach rechts, von oben nach unten, als würde man einen Absatz lesen. Besuchen Sie beim Besuch jedes Elements auch das entsprechende Element, das beim umgekehrten Besuch der Untermatrix besucht werden würde. Für jedes besuchte Element UND seinen Wert in die Stelle, an der seine Zeile die erste Spalte kreuzt, und auch UND seinen Wert in die Stelle, an der seine Spalte die erste Zeile kreuzt.
  • Sobald das Zentrum der Submatrix erreicht ist, besuchen Sie die beiden Elemente weiterhin wie oben gleichzeitig. Setzen Sie nun jedoch den Wert der besuchten Elemente auf das UND, an dem die Zeile die erste Spalte kreuzt und an dem die Spalte die erste Zeile kreuzt. Danach ist die Untermatrix vollständig.
  • Verwenden Sie die beiden zu Beginn berechneten booleschen Variablen, um die erste Zeile und die erste Spalte auf ihre korrekten Werte zu setzen.

Templatisierte 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;
}
Apriori
quelle
0

Ok, mir ist klar, dass es kein gutes Spiel ist, aber ich habe es in einem Durchgang mit einem Bool und einem Byte anstelle von zwei Bools bekommen ... schließen. Ich würde auch nicht für die Effizienz bürgen, aber diese Art von Fragen erfordern oft weniger als optimale 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; }
        }
    }
}
Walery Strauch
quelle
0

Sie können dies in einem Durchgang sortieren - wenn Sie den Zugriff auf die Matrix nicht in der Reihenfolge des wahlfreien Zugriffs zählen, wodurch die Vorteile eines einzelnen Durchgangs (Cache-Kohärenz / Speicherbandbreite) entfallen.

[bearbeiten: einfache, aber falsche Lösung gelöscht]

Sie sollten eine bessere Leistung als jede Methode mit einem Durchgang erzielen, indem Sie dies in zwei Durchgängen tun: einem zum Sammeln von Zeilen- / Spalteninformationen und einem zum Anwenden. Auf das Array (in Zeilen-Hauptreihenfolge) wird kohärent zugegriffen; Bei Arrays, die die Cache-Größe überschreiten (deren Zeilen jedoch in den Cache passen), sollten Daten zweimal aus dem Speicher gelesen und einmal gespeichert 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;
        }
    }
}
kommender Sturm
quelle
0

Die einfachste Lösung, die ich mir vorstellen kann, wird unten eingefügt. Die Logik besteht darin, aufzuzeichnen, welche Zeile und Spalte während der Iteration auf Null gesetzt werden soll.

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);
    }
}
Geekprogrammer
quelle
0

Hier ist meine Ruby-Implementierung mit dem Test enthalten. Dies würde O (MN) Speicherplatz beanspruchen. Wenn wir eine Echtzeitaktualisierung wünschen (um die Ergebnisse anzuzeigen, wenn wir Nullen finden, anstatt auf die erste Schleife zum Finden von Nullen zu warten), können wir einfach eine andere Klassenvariable erstellen, wie @outputund wann immer wir eine Null finden, die wir aktualisieren @outputund 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
Eki Eqbal
quelle
0

Der folgende Code erstellt eine Matrix der Größe m, n. Entscheiden Sie zuerst die Abmessungen der Matrix. Ich wollte die Matrix [m] [n] zufällig mit Zahlen zwischen 0 und 10 füllen. Erstellen Sie dann eine weitere Matrix mit denselben Abmessungen und füllen Sie sie mit -1s (endgültige Matrix). Durchlaufen Sie dann die Anfangsmatrix, um festzustellen, ob Sie 0 treffen. Wenn Sie auf Position (x, y) klicken, gehen Sie zur endgültigen Matrix und füllen Sie die Zeile x mit 0s und die Spalte y mit 0s. Lesen Sie am Ende die endgültige Matrix durch. Wenn der Wert -1 (ursprünglicher Wert) ist, kopieren Sie den Wert an derselben Stelle der anfänglichen Matrix nach final.

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;
}
user3743369
quelle
Sie geben dem von Ihnen geposteten Code keine Erklärung oder keinen Kontext.
Aaron
Hoffe das ist jetzt besser. Danke für die Warnung. Ich würde gerne mehr erklären, wenn es Ihnen nicht klar ist.
user3743369
0

Hier ist meine Lösung. Wie Sie dem Code entnehmen können, setzt er bei einer M * N-Matrix die gesamte Zeile auf Null, sobald er eine Null in dieser Zeile überprüft. Die zeitliche Komplexität meiner Lösung beträgt O (M * N). Ich teile die gesamte Klasse, die ein statisch bestücktes Array zum Testen und eine Display-Array-Methode hat, um 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("");
    }

}

}}

Türkmen Mustafa Demirci
quelle