Définissez chaque cellule de la matrice sur 0 si cette ligne ou colonne contient un 0

Étant donné une matrice NxN avec 0 et 1. Définissez chaque ligne contenant a 0sur tous les 0s et définissez toutes les colonnes contenant a 0sur tous les 0s.

Par exemple

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

résulte en

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

Un ingénieur Microsoft m'a dit qu'il existe une solution qui n'implique aucune mémoire supplémentaire, juste deux variables booléennes et une passe, donc je cherche cette réponse.

BTW, imaginez que c'est une matrice de bits, donc seuls les 1 et les 0 peuvent être dans la matrice.

Ok, donc je suis fatigué car il est 3 heures du matin ici, mais j'ai un premier essai en place avec exactement 2 passes sur chaque nombre de la matrice, donc en O (NxN) et c'est linéaire dans la taille de la matrice.

J'utilise la 1ère colonne et la première ligne comme marqueurs pour savoir où sont les lignes / cols avec seulement 1. Ensuite, il y a 2 variables l et c pour se souvenir si la 1ère ligne / colonne sont toutes des 1 également. Ainsi, la première passe définit les marqueurs et réinitialise le reste à 0.

La deuxième passe définit 1 aux endroits où les lignes et les colonnes sont marquées comme étant 1, et réinitialise la 1ère ligne / colonne en fonction de l et c.

Je doute fortement que je puisse être fait en 1 passage car les carrés au début dépendent des carrés à la fin. Peut-être que mon 2ème passage peut être rendu plus efficace ...

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)

Cela ne peut pas être fait en une seule passe car un seul bit a un effet sur les bits avant et après lui dans n'importe quel ordre. Quel que soit l'ordre dans lequel vous parcourez le tableau, vous pouvez plus tard tomber sur un 0, ce qui signifie que vous devez revenir en arrière et changer un 1 précédent en 0.

Mettre à jour

Les gens semblent penser qu'en limitant N à une valeur fixe (disons 8), vous pouvez résoudre ce problème en une seule passe. Eh bien, c'est a) manquer le point et b) pas la question d'origine. Je ne publierais pas de question sur le tri et j'attendrais une réponse commençant "en supposant que vous ne vouliez trier que 8 choses ...".

Cela dit, c'est une approche raisonnable si vous savez que N est en fait limité à 8. Ma réponse ci-dessus répond à la question initiale qui n'a pas une telle restriction.

Mon idée est donc d'utiliser les valeurs de la dernière ligne / colonne comme indicateur pour indiquer si toutes les valeurs de la colonne / ligne correspondante sont des 1.

En utilisant un balayage Zig Zag sur toute la matrice SAUF la dernière ligne / colonne. À chaque élément, vous définissez la valeur dans la dernière ligne / colonne comme le ET logique de lui-même avec la valeur de l'élément actuel. En d'autres termes, si vous atteignez un 0, la dernière ligne / colonne sera définie sur 0. Si vous avez un 1, la valeur de la dernière ligne / colonne sera 1 seulement si elle était déjà 1. Dans tous les cas, définissez l'élément actuel sur 0.

Lorsque vous avez terminé, votre dernière ligne / colonne doit avoir des 1 si la colonne / ligne correspondante est remplie de 1.

Effectuez un balayage linéaire de la dernière ligne et de la dernière colonne et recherchez les 1. Définissez des 1 dans les éléments correspondants dans le corps de la matrice où la dernière ligne et la dernière colonne sont toutes deux des 1.

Le codage sera difficile pour éviter les erreurs ponctuelles, etc., mais cela devrait fonctionner en un seul passage.

J'ai une solution ici, elle s'exécute en un seul passage, et fait tout le traitement "en place" sans mémoire supplémentaire (sauf pour agrandir la pile).

Il utilise la récursivité pour retarder l'écriture des zéros, ce qui détruirait bien sûr la matrice pour les autres lignes et 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();
}

Je ne pense pas que ce soit faisable. Lorsque vous êtes sur le premier carré et que sa valeur est 1, vous n'avez aucun moyen de savoir quelles sont les valeurs des autres carrés de la même ligne et colonne. Vous devez donc les vérifier et s'il y a un zéro, revenez au premier carré et changez sa valeur en zéro. Je recommande de le faire en deux passes - la première passe rassemble des informations sur les lignes et les colonnes qui doivent être mises à zéro (les informations sont stockées dans un tableau, nous utilisons donc de la mémoire supplémentaire). La deuxième passe modifie les valeurs. Je sais que ce n'est pas la solution que vous recherchez, mais je pense que c'est une solution pratique. Les contraintes que vous donnez rendent le problème insoluble.

Je peux le faire avec deux variables entières et deux passes (jusqu'à 32 lignes et colonnes ...)

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

le problème peut être résolu en un seul passage

sauvegarde de la matrice dans un tableau i X j.

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 .

maintenant imprimer toutes les valeurs comme 0 pour les valeurs de i et j enregistrées dans a et b le reste des valeurs est 1 c'est-à-dire (3,3) (3,4) (5,3) et (5,4)

Une autre solution qui prend deux passes, consiste à accumuler les ET horizontalement et verticalement:

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    

Je pensais pouvoir concevoir un tel algorithme en utilisant des bits de parité , des codes de Hamming ou une programmation dynamique , en utilisant éventuellement ces deux booléens comme nombre à 2 bits, mais je n'ai pas encore réussi.

Pouvez-vous s'il vous plaît revérifier l'énoncé du problème avec votre ingénieur et nous le faire savoir? S'il est en effet une solution, je veux garder grignote le problème.

Gardez une seule variable pour garder une trace de ce que sont toutes les lignes ET ensemble.

Si une ligne vaut -1 (tous les 1), alors faites de la ligne suivante une référence à cette variable

Si une ligne est autre chose, c'est un 0. Vous pouvez tout faire en un seul passage. Code pseudo:

foreach (my $row) rows {
     $andproduct = $andproduct & $row;
     if($row != -1) {
        zero out the row
     }  else {
        replace row with a reference to andproduct
     }
}

Cela devrait le faire, en une seule passe - mais il y a une hypothèse ici que N est suffisamment petit pour que le processeur fasse de l'arithmétique sur une seule ligne, sinon vous devrez boucler sur chaque ligne pour déterminer si tout est 1s ou pas, je crois. Mais étant donné que vous posez des questions sur les algos et que vous ne contraignez pas mon matériel, je commencerais simplement ma réponse par "Construisez un processeur prenant en charge l'arithmétique N-bit ..."

Voici un exemple de la façon dont cela peut être fait en C. Remarque Je soutiens que les valeurs et arr pris ensemble représentent le tableau, et p et numproduct sont mon itérateur et les variables de produit AND utilisent pour implémenter le problème. (J'aurais pu faire une boucle sur arr avec l'arithmétique du pointeur pour valider mon travail, mais une fois c'était suffisant!)

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;
}

Cela produit 0, 0, 6, 0, 6, qui est le résultat pour les entrées données.

Ou en PHP, si les gens pensent que mes jeux de pile en C trichent (je vous suggère que ce n'est pas le cas, car je devrais pouvoir stocker la matrice comme je veux):

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

Est-ce que je manque quelque chose?

Beau défi. Cette solution utilise en quelque sorte seulement deux booléens créés sur la pile, mais les booléens sont créés plusieurs fois sur la pile car la fonction est récursive.

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;
}

Cela scanne dans un modèle comme:

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

etc

Et puis changer les valeurs de ce modèle au retour sur chacune des fonctions de scan. (De bas en haut):

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

etc

Ok, c'est une solution qui

• utilise une seule valeur extra longue pour le stockage de travail.
• n'utilise aucune récursivité.
• une passe de seulement N, pas même N * N.
• fonctionnera pour d'autres valeurs de N mais nécessitera de nouvelles #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;
    }

Réellement. Si vous voulez simplement exécuter l'algorithme et imprimer les résultats (c'est-à-dire ne pas les restaurer, alors cela peut facilement être fait en un seul passage. Le problème survient lorsque vous essayez de modifier le tableau pendant que vous exécutez l'algorithme.

Voici ma solution. Il s'agit simplement de mettre en ET les valeurs de lignes / colonnes pour un élément de givein (i, j) et de l'imprimer.

#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;
    }
}

J'ai essayé de résoudre ce problème en C #.

J'ai utilisé deux variables de boucle (i et j) en dehors de la matrice réelle et n représentant sa dimension

La logique que j'ai essayée est de:

1. Calculer ET pour les lignes et les colonnes impliquées dans chaque carré concentrique de la matrice
2. Stockez-le dans ses cellules d'angle (je les ai stockés dans le sens anti-horaire)
3. Deux variables booléennes sont utilisées pour conserver les valeurs de deux coins lors de l'évaluation d'un carré particulier.
4. Ce processus prendrait fin lorsque la boucle externe (i) est à mi-chemin.
5. Évaluez les résultats des autres cellules en fonction des cellules du coin (pour le reste de i). Ignorez les cellules d'angle pendant ce processus.
6. Quand i atteint n, toutes les cellules auront son résultat à l'exception des cellules d'angle.
7. Mettez à jour les cellules d'angle. Il s'agit d'une itération supplémentaire d'une longueur de n / 2 autre que la contrainte de passe unique mentionnée dans le problème.

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;
            }
        }
    }
}

One Pass - J'ai parcouru l'entrée une seule fois, mais j'ai utilisé un nouveau tableau et seulement deux variables booléennes supplémentaires.

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

    }

Bien que cela soit impossible compte tenu des contraintes, le moyen le plus efficace de le faire en termes d'espace consiste à traverser la matrice de manière chevauchante et alternée de lignes / colonnes, ce qui donnerait un motif similaire à la pose de briques en zig-zag:

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

En utilisant cela, vous iriez dans chaque ligne / colonne, comme indiqué, et si vous rencontrez un 0 à tout moment, définissez une variable booléenne et parcourez à nouveau cette ligne / colonne, en définissant les entrées sur 0 au fur et à mesure.

Cela ne nécessitera aucune mémoire supplémentaire et n'utilisera qu'une seule variable booléenne. Malheureusement, si le bord "lointain" est défini sur 0, c'est le pire des cas et vous parcourez l'ensemble du tableau deux fois.

créer une matrice de résultats et définir toutes les valeurs sur 1. parcourir la matrice de données dès qu'un 0 est rencontré, définir la colonne de ligne de matrice de résultats sur 0

À la fin du premier passage, la matrice de résultats aura la bonne réponse.

Ça a l'air assez simple. Y a-t-il un truc qui me manque? N'êtes-vous pas autorisé à utiliser un jeu de résultats?

ÉDITER:

Cela ressemble à une fonction F #, mais c'est un peu triche car même si vous faites une seule passe, la fonction peut être récursive.

Il semble que l'intervieweur essaie de déterminer si vous connaissez la programmation fonctionnelle.

Eh bien, j'ai proposé une solution en place (non récursive) en un seul passage utilisant 4 booléens et 2 compteurs de boucle. Je n'ai pas réussi à le réduire à 2 bools et 2 ints, mais je ne serais pas surpris si c'était possible. Il fait environ 3 lectures et 3 écritures de chaque cellule, et il devrait être O (N ^ 2) ie. linéaire dans la taille du tableau.

Il m'a fallu quelques heures pour résoudre celui-ci - je ne voudrais pas avoir à le trouver sous la pression d'une interview! Si j'ai fait un booboo, je suis trop fatigué pour le repérer ...

Euh ... Je choisis de définir "single-pass" comme faisant un balayage à travers la matrice, plutôt que de toucher chaque valeur une fois! :-)

#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;
}

j'espère que vous apprécierez ma solution c # en 1 passage

vous pouvez récupérer un élément avec O (1) et n'avez besoin que de l'espace d'une ligne et d'une colonne de la matrice

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 passage, 2 booléens. Je dois juste supposer que les index entiers dans les itérations ne comptent pas.

Ce n'est pas une solution complète mais je ne peux pas passer ce point.

Si je pouvais seulement déterminer si un 0 est un 0 original ou un 1 qui a été converti en 0, je n'aurais pas à utiliser des -1 et cela fonctionnerait.

Ma sortie est comme ceci:

-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

L'originalité de mon approche consiste à utiliser la première moitié de l'examen d'une ligne ou d'une colonne pour déterminer si elle contient un 0 et la dernière moitié pour définir les valeurs - cela se fait en regardant x et width-x puis y et height -y à chaque itération. Sur la base des résultats de la première moitié de l'itération, si un 0 dans la ligne ou la colonne a été trouvé, j'utilise la dernière moitié de l'itération pour changer les 1 en -1.

Je viens de réaliser que cela pouvait être fait avec seulement 1 booléen laissant 1 à ...?

Je publie ceci en espérant que quelqu'un dira: "Ah, fais juste ça ..." (Et j'ai passé beaucoup trop de temps dessus pour ne pas poster.)

Voici le code en 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

Personne n'utilise des formes binaires? puisque ce n'est que 1 et 0. Nous pouvons utiliser des vecteurs binaires.

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

Voici le 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)

Et la sortie:

Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110

Vous pouvez faire quelque chose comme ceci pour utiliser une passe mais une matrice d'entrée et de sortie:

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

où col(xy)sont les bits dans la colonne contenant le point xy; row(xy)correspond aux bits de la ligne contenant le point xy. nest la taille de la matrice.

Ensuite, faites une boucle sur l'entrée. Peut-être extensible pour être plus efficace en termes d'espace?

Un scan matriciel, deux booléens, pas de récursivité.

Comment éviter le deuxième passage? La deuxième passe est nécessaire pour effacer les lignes ou les colonnes lorsque le zéro apparaît à leur fin.

Cependant, ce problème peut être résolu, car lorsque nous analysons la ligne #i, nous connaissons déjà l'état de la ligne # i-1. Ainsi, pendant que nous analysons la ligne #i, nous pouvons simultanément effacer la ligne # i-1 si nécessaire.

La même solution fonctionne pour les colonnes, mais nous devons analyser les lignes et les colonnes simultanément pendant que les données ne sont pas modifiées par l'itération suivante.

Deux booléens sont nécessaires pour stocker l'état de la première ligne et de la première colonne, car leurs valeurs seront modifiées lors de l'exécution de la partie principale de l'algorithme.

Pour éviter d'ajouter plus de booléens, nous stockons l'indicateur "clear" pour les lignes et colonnes de la première ligne et colonne de la matrice.

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

semble que ce qui suit fonctionne sans aucune exigence d'espace supplémentaire:

notez d'abord que multiplier les éléments de la ligne par les éléments de la ligne dans laquelle se trouve un élément, donne la valeur souhaitée.

Afin de ne pas utiliser d'espace supplémentaire (ne pas créer une nouvelle matrice et la remplir, mais appliquer les modifications directement à la matrice), commencez en haut à gauche de la matrice et faites le calcul pour toute matrice ixi (qui "commence" à (0 , 0)) avant de considérer tout élément avec un indice> i.

j'espère que cela fonctionne (havent testet)

Ceci est TESTÉ pour différents N en C ++, et est:
UN PASS , DEUX BOOLS , PAS DE RÉCURSION , PAS DE MÉMOIRE SUPPLÉMENTAIRE , TENUE POUR ARBITRARLY LARGE N
(Jusqu'à présent, aucune des solutions ici ne fait TOUTES celles-ci.)

Plus précisément, je suis amusant que les compteurs de deux boucles fonctionnent. J'ai deux const unsigneds, qui n'existent que plutôt que d'être calculés à chaque fois pour la lisibilité. L'intervalle de la boucle externe est [0, N] et l'intervalle de la boucle interne est [1, n - 1]. L'instruction switch est dans la boucle existe principalement pour montrer très clairement qu'il ne s'agit en réalité que d'un seul passage.

Stratégie d'algorithme:

La première astuce est pour nous une ligne et une colonne de la matrice elle-même pour accumuler le contenu de la matrice, cette mémoire devient disponible en déchargeant tout ce que nous avons vraiment besoin de savoir de la première ligne et colonne dans deux booléens. La deuxième astuce consiste à obtenir deux passes sur une, en utilisant la symétrie de la sous-matrice et ses indices.

Synopsis de l'algorithme:

• Scannez la première ligne et stockez si elles sont toutes des unités dans un booléen, faites de même pour la première colonne stockant le résultat dans un deuxième booléen.
• Pour la sous-matrice excluant la première ligne et la première colonne: parcourir, de gauche à droite, de haut en bas, comme on lirait un paragraphe. Lors de la visite de chaque élément, visitez également l'élément correspondant qui serait visité si vous visitez la sous-matrice à l'envers. Pour chaque élément visité ET sa valeur dans l'endroit où sa ligne traverse la première colonne, et aussi ET sa valeur dans l'endroit où sa colonne croise la première ligne.
• Une fois le centre de la sous-matrice atteint, continuez à visiter les deux éléments simultanément comme ci-dessus. Cependant, définissez maintenant la valeur des éléments visités sur le ET de l'endroit où sa ligne traverse la première colonne et de l'endroit où sa colonne croise la première ligne. Après cela, la sous-matrice est complète.
• Utilisez les deux variables booléennes calculées au début pour définir la première ligne et la première colonne sur leurs valeurs correctes.

Implémentation en modèle C ++:

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, je me rends compte que ce n'est pas tout à fait une correspondance, mais je l'ai obtenu en un seul passage en utilisant un booléen et un octet au lieu de deux booléens ... fermer. Je ne garantirais pas non plus son efficacité, mais ces types de questions nécessitent souvent des solutions moins qu'optimales.

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; }
        }
    }
}

Vous pouvez le faire en un seul passage - si vous ne comptez pas accéder à la matrice dans un ordre d'accès aléatoire, ce qui élimine les avantages de le faire en un seul passage en premier lieu (cohérence du cache / bande passante mémoire).

[modifier: solution simple, mais incorrecte supprimée]

Vous devriez obtenir de meilleures performances que n'importe quelle méthode en un seul passage en le faisant en deux passes: une pour accumuler les informations de ligne / colonne et une pour l'appliquer. Le tableau (dans l'ordre des lignes principales) est accessible de manière cohérente; pour les tableaux dépassant la taille du cache (mais dont les lignes peuvent tenir dans le cache), les données doivent être lues à partir de la mémoire deux fois et stockées une fois:

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;
        }
    }
}

La solution la plus simple à laquelle je puisse penser est collée ci-dessous. La logique consiste à enregistrer la ligne et la colonne à mettre à zéro lors de l'itération.

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

Voici mon implémentation Ruby avec le test inclus, cela prendrait de l'espace O (MN). Si nous voulons une mise à jour en temps réel (comme pour afficher les résultats lorsque nous trouvons des zéros plutôt que d'attendre la première boucle de recherche de zéros), nous pouvons simplement créer une autre variable de classe comme @outputet chaque fois que nous trouvons un zéro, nous mettons à jour @outputet non @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

Le code ci-dessous crée une matrice de taille m, n. Décidez d'abord des dimensions de la matrice. Je voulais remplir la matrice [m] [n] de façon aléatoire avec des nombres entre 0..10. Créez ensuite une autre matrice de mêmes dimensions et remplissez-la de -1s (matrice finale). Ensuite, parcourez la matrice initiale pour voir si vous atteindrez 0. Lorsque vous frappez sur l'emplacement (x, y), allez à la matrice finale et remplissez la ligne x avec des 0 et la colonne y avec des 0. À la fin, lisez la matrice finale, si la valeur est -1 (valeur d'origine), copiez la valeur au même emplacement de la matrice initiale vers 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;
}

voici ma solution. Comme vous pouvez le voir dans le code, étant donné une matrice M * N, il met la ligne entière à zéro une fois qu'il inspecte un zéro dans cette ligne.la complexité temporelle de ma solution est O (M * N). Je partage toute la classe qui a un tableau rempli statique pour les tests et une méthode de tableau d'affichage pour voir le résultat dans la console.

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

}

}