Définir chaque cellule de la matrice à 0 si la ligne ou la colonne contient un 0

Ok, donc, je suis fatigué comme il est 3H du matin ici, mais j'ai d'abord essayer en place avec exactement 2 passes sur chaque nombre dans la matrice, donc en O(NxN) et il est linéaire en la taille de la matrice.

J'utilise la 1ère colonne et la première ligne en tant que marqueurs de savoir où sont rangées/colonnes avec seulement 1. Ensuite, il y a 2 variables l et de c à vous rappeler si la 1ère ligne/colonne sont tous les 1 aussi.
Ainsi, le premier passage ensembles de marqueurs et réinitialise le reste à 0.

La seconde passe jeux 1 dans les endroits où les lignes et les colonnes marquées à 1, et réinitialise la 1ère ligne/col en fonction de l et c.

Je doute fortement que j'ai peut être fait en 1 passe que des carrés dans le début dépendent de places à la fin. Peut-être mon 2ème passe peut être rendue 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)

Donc, mon idée est d'utiliser les valeurs dans la dernière rangée/colonne comme un drapeau pour indiquer si toutes les valeurs dans la colonne correspondante/ligne sont 1s.

À l'aide d'un Zig Zag scan à travers l'ensemble de la matrice à l'EXCEPTION de la dernière rangée/colonne. À chaque élément, vous définissez la valeur de la dernière rangée/colonne de la logique ET de lui-même avec la valeur de l'élément courant. En d'autres termes, si vous frappez un 0, la dernière rangée/colonne est définie à 0. Si vous avez un 1, la valeur de la dernière rangée/colonne 1 que si c'était le 1 déjà. En tout cas, réglez l'élément courant à 0.

Lorsque vous avez terminé, votre dernière rangée/colonne doit avoir 1 ssi le correspondant de la colonne/ligne a été rempli avec 1s.

Faire une analyse linéaire à travers la dernière rangée et de la colonne et de la recherche de 1s. Jeu de 1s dans les éléments correspondants dans le corps de la matrice où la dernière rangée et de colonne sont à la fois 1s.

De codage, il sera difficile d'éviter les hors-en-un, des erreurs, etc, mais il devrait fonctionner en un seul passage.

Je ne pense pas que c'est faisable. Lorsque vous êtes sur la première place et sa valeur est 1, vous n'avez aucun moyen de savoir ce que les valeurs des autres places dans la même rangée et de colonne. Donc, vous avez pour vérifier celles et si il y a un zéro, revenir à la première place et changer sa valeur à zéro. Je vais vous recommandons de le faire en deux fois - la première passe rassemble des informations sur les lignes et les colonnes doivent être mis à zéro (les informations sont stockées dans un tableau, nous sommes donc à l'aide de certains de mémoire supplémentaire). La seconde passe de modifier les valeurs. Je sais que ce n'est pas la solution que vous cherchez, mais je pense que c'est une pratique. Les contraintes donné par vous rendre le problème insoluble.

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

économie de la matrice dans un i X j de la matrice.

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 à 0 pour les valeurs de i et j enregistré en a et b
reste des valeurs sont 1 ie (3,3) (3,4) (5,3) et (5,4)

Garder une seule variable pour garder une trace de ce que toutes les lignes ANDed sont ensemble.

Si une ligne est -1 (toutes les 1 s), puis de faire la ligne suivante, une référence à cette variable

Si une ligne est une chose mais, c'est un 0. Vous pouvez faire tout en un seul passage. Pseudo-code:

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

Qui devrait le faire, en un seul passage-mais il s'agit d'une hypothèse ici que N est assez petit pour le CPU pour faire de l'arithmétique sur une seule ligne, sinon vous allez avoir besoin de faire une boucle sur chaque ligne pour déterminer si c'est tous les 1 ou pas, je crois. Mais étant donné que vous demandez sur les algos et ne gênant pas mon matériel, je viens de commencer ma réponse à "Construire un CPU qui supporte à N bits de l'arithmétique..."

Voici un exemple de comment cela peut être fait en C. Remarque, je soutiens que les valeurs et l'arr pris ensemble représentent la matrice, et p et numproduct sont mes itérateur et ET produit des variables à utiliser pour implémenter le problème. (J'aurais pu en boucle sur arr avec l'arithmétique des pointeurs pour valider mon travail, mais une fois a suffit!)

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

Ce produit 0, 0, 6, 0, 6, qui est le résultat de la donnée d'intrants.

Ou en PHP, si les gens pensent que ma pile de jeux en C sont de la triche (je vous suggérer que ce n'est pas parce que je devrais être capable de stocker la matrice de n'importe quelle manière que je s'il vous plaît):

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

Suis-je raté quelque chose?

D'accord c'est une solution qui

• utilise seulement un extra-longues de la valeur pour la mémoire de travail.
• n'utilise pas la récursivité.
• un passage de seulement N, pas même N*N.
• va travailler pour d'autres valeurs de N, mais aura besoin de nouveaux #définit.

#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]='
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;
}
';
    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;
    }

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

J'ai utilisé deux variables de boucle (i et j), à l'exception de la matrice et n représente sa dimension

Logique que j'ai essayé est de:

1. Calculer ET pour les lignes et les colonnes concernées dans chaque carrées concentriques de la matrice
2. Le ranger dans son coin cellules (que j'ai stockées dans le sens anti-horaire afin)
3. Deux bool variables sont utilisées pour conserver les valeurs de deux coins lors de l'évaluation d'un particulier carrés.
4. Ce processus prendrait fin lors de la boucle externe (i) est à mi-chemin.
5. Évaluer les résultats des autres sur la base de cellules les cellules d'angle (pour le repos de je). Passez le coin des cellules au cours de ce processus.
6. Quand j'ai atteint n, toutes les cellules de son résultat, sauf pour le coin des cellules.
7. Mise à jour le coin des cellules. C'est une itération supplémentaire à longueur de n/2 autres que le seul passage de la contrainte 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;
            }
        }
    }
}

créer une matrice de résultats et de définir toutes les valeurs de 1.
aller par le biais de la matrice de données dès qu'un 0 est rencontré, définir le résultat lignes de la matrice colonne à 0

À la fin de la première passe, le résultat de la matrice aura la bonne réponse.

A l'air assez simple. Est-il un truc que je suis absent? Vous n'êtes pas autorisé à utiliser un ensemble de résultats?

EDIT:

Ressemble à une fonction F#, mais c'est de la triche un peu car, même si vous faites un seul passage, la fonction peut être récursive.

Il ressemble à l'intervieweur est à essayer de comprendre si vous connaissez la programmation fonctionnelle.

j'espère que vous apprécierez ma 1 passe-solution c#

vous pouvez récupérer un élément de O(1), et seulement besoin 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
*/

Personne n'est à l'aide de formes binaires? car c'est seulement de 1 et de 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

Une matrice d'analyse, deux booléens, pas de récursivité.

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

Toutefois, ce problème peut être résolu, parce que lorsque l'on analyse la ligne #i nous savons déjà le statut de ligne pour la ligne #i-1. Ainsi, alors que nous sommes de la numérisation de la ligne #i nous pouvons simultanément claire la ligne #i-1 si c'est nécessaire.

La même solution fonctionne pour les colonnes, mais nous avons besoin de balayage des lignes et des colonnes simultanément alors que les données n'est pas modifié par l'itération suivante.

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

Pour éviter l'ajout de plus de booléens nous sommes le stockage de l' "clair" drapeau pour les lignes et les colonnes dans la première rangée et de 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();
}

C'est TESTÉ pour différentes N en C++, et est:

UN PASSAGE, DEUX BOOLÉENS, PAS DE RÉCURSIVITÉ, PAS DE MÉMOIRE SUPPLÉMENTAIRE, DÉTIENT POUR ARBITRARLY UN GRAND N

(Jusqu'à présent, aucune des solutions ne TOUTES ces.)

Plus spécifiquement, je suis amusant, deux compteurs de boucle sont d'accord. J'ai deux const unsigneds, qui n'existent que plutôt que d'être calculées à chaque fois pour des raisons de lisibilité. La boucle externe de l'intervalle [0, N], et la boucle interne de l'intervalle [1, n - 1]. L'instruction switch est dans la boucle pour la plupart montrent très clairement que c'est vraiment un passage.

Algorithme De Stratégie:

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

Algorithme Synopsis:

• Analyse de la première ligne et en magasin si ils sont tous dans un booléen, faites de même pour la première colonne de stocker le résultat dans une deuxième valeur de type boolean.
• Pour la sous-matrice à l'exclusion de la première ligne et la première colonne: itérer, de gauche à droite, de haut en bas, comme on lirait un paragraphe. Lors d'une visite à chaque élément, visitez également le correspondant élément susceptible d'être visité si la visite de la sous-matrice dans le sens inverse. Pour chaque élément visité ET de sa valeur dans le où sa ligne traverse la première colonne, et aussi, ET sa valeur, d'où sa colonne franchit la première ligne.
• Une fois que le centre de la sous-matrice est atteint, continuer à visiter les deux éléments simultanément comme ci-dessus. Cependant maintenant définir l'visité des éléments de la valeur à la ET de où les de son la ligne traverse la première colonne, et d'où sa colonne franchit la première ligne. Après cela, la sous-matrice est terminée.
• Utiliser les deux variables booléennes calculée à la mendicité pour définir la première ligne et la première colonne à leurs valeurs correctes.

Templatized C++ Mise En Œuvre:

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

Vous pouvez sorta de le faire en une seule passe, si vous ne comptez pas l'accès de la matrice d'accès aléatoire de l'ordre, ce qui élimine les avantages de le faire en une seule passe, en premier lieu (cache-cohérence/la mémoire de la bande passante).

[edit: simple, mais mauvaise solution supprimé]

Vous devriez obtenir une meilleure performance que tout seul passage par la méthode de le faire en deux passages: l'un à accumuler de la ligne/colonne d'infos, et un pour l'appliquer. Le tableau (en ligne ordre majeur) est accessible de façon cohérente, et pour les tableaux dépassement de la taille de la mémoire 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és qu'une seule 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;
        }
    }
}

Voici mon Ruby mise en œuvre avec le test inclus, Ce serait de prendre en O(MN) de l'espace. Si nous voulons une véritable mise à jour en temps (comme pour montrer les résultats lorsque nous découvrirons des zéros plutôt que d'attendre que la première boucle de trouver des zéros), il nous suffit de créer une autre variable de classe comme @output et chaque fois que nous trouvons un zéro à la mise à @output et pas @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

voici ma solution. Comme vous pouvez le voir dans le code, donné une M * N de la matrice, il définit l'ensemble de la ligne de zéro une fois qu'il inspecte un zéro en ligne.la complexité du temps de ma solution est de O(M * N) .
Je partage l'ensemble de la classe qui a une statique peuplé de tableau pour le test et un affichage de la méthode de la baie 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("");
    }

}

}

Définir un indicateur (un numéro qui est de contraindre j'utilise ici -1) puis une fois que nous changeons tous de ligne correspondante et le col , remplacer tous les drapeau à zéro

public class Main {

        public static void main(String[] args) {


            //test case 1
            int[][] multi = new int[][]{
                    { 1, 2, 3 },
                    { 4, 0, 5 },
                    { 0, 6, 7 },
            };

            //test case 2
            int[][] multi2 = new int[][]{
                    { 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},
            };

            TwoDArraySetZero(multi2);
        }



        static  void  TwoDArraySetZero(int[][] array){

            //iterate through all elements
            for(int i = 0 ; i <= array.length-1 ; i++){
                for (int j = 0; j <= array.length-1; j++) {

                    //checking if match with zero
                    if (array[i][j] == 0){

                        //set replace with -1 all matching zero row and col if not zero
                        for (int k = 0; k <= array.length-1 ; k++) {
                            if(array[i][k] != 0 )
                                array[i][k] = -1;
                            if(array[k][j] != 0)
                                array[k][j]= -1;
                        }
                    }
                }
            }


            //print array
            for(int i = 0; i <= array.length-1; i++)
            {
                for(int j = 0; j <= array.length-1; j++)
                {
                    //replace with zero all -1

                    if(array[i][j] == -1)
                        array[i][j] = 0;

                    System.out.printf("%5d ", array[i][j]);
                }
                System.out.println();
            }

        }

    }