Mettre chaque cellule de la matrice à 0 si cette ligne ou cette colonne contient un 0

Question

Étant donné une matrice NxN avec des 0 et des 1. Définissez chaque ligne qui contient un 0 à tous 0 et définir chaque colonne qui contient un 0 à tous 0 s.

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 de Microsoft m'a dit qu'il existe une solution qui n'implique aucune mémoire supplémentaire, juste deux variables booléennes et un passage, donc je cherche cette réponse.

Par ailleurs, imaginez qu'il s'agit d'une matrice de bits, donc seuls les 1 et les 0 sont autorisés dans la matrice.

Answer 1

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

J'utilise la première colonne et la première ligne comme marqueurs pour savoir où se trouvent les lignes/cols contenant uniquement des 1. Ensuite, il y a deux variables l et c pour se rappeler si la première ligne/colonne contient aussi des 1. Ainsi, la première passe définit les marqueurs et réinitialise le reste à 0.

La deuxième passe met 1 aux endroits où les lignes et les colonnes ont été marquées pour être 1, et remet à zéro la première ligne/col en fonction de l et c.

Je doute fortement que je puisse être fait en 1 passe car les carrés du début dépendent des carrés de la fin. Peut-être que ma 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)

Answer 2

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

Mise à jour

Les gens semblent penser qu'en limitant N à une valeur fixe (disons 8), on peut résoudre ce problème en une seule fois. Eh bien, c'est a) passer à côté de l'essentiel et b) ne pas répondre à la question initiale. Je ne posterais pas une question sur le tri en m'attendant à une réponse qui commencerait par "en supposant que vous ne voulez 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 ne comporte pas une telle restriction.

Answer 3

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

Utilisation d'un Scanning zig zag dans toute la matrice SAUF dans la dernière ligne/colonne. À chaque élément, vous définissez la valeur de la dernière ligne/colonne comme étant le ET logique de cette dernière avec la valeur de l'élément actuel. En d'autres termes, si vous obtenez un 0, la dernière ligne/colonne sera mise à 0. Si vous obtenez un 1, la valeur de la dernière ligne/colonne sera 1 uniquement si elle était déjà 1. Dans tous les cas, définissez l'élément actuel à 0.

Lorsque vous avez terminé, votre dernière ligne/colonne devrait comporter des 1 si la colonne/ligne correspondante était remplie de 1.

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

Le codage sera délicat pour éviter les erreurs de type "off-by-one", etc. mais il devrait fonctionner en un seul passage.

Answer 4

J'ai une solution ici, elle s'exécute en une seule passe, et fait tout le traitement "en place" sans mémoire supplémentaire (sauf pour faire croître la pile).

Il utilise la récursion pour retarder l'écriture des zéros, ce qui bien sûr détruirait la matrice pour les autres lignes et colonnes :

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

Answer 5

Je ne pense pas que ce soit faisable. Lorsque vous êtes sur la première case et que sa valeur est 1, vous n'avez aucun moyen de savoir quelles sont les valeurs des autres cases de la même ligne et de la même colonne. Vous devez donc les vérifier et, s'il y a un zéro, revenir au premier carré et changer sa valeur en zéro. Je vous recommande de le faire en deux passes - la première passe rassemble les informations sur les lignes et les colonnes qui doivent être mises à zéro (les informations sont stockées dans un tableau, nous utilisons donc un peu plus de mémoire). 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 avez données rendent le problème insoluble.