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

Étant donné une masortingce NxN avec 0 et 1. Définissez chaque ligne contenant un 0 à tous les 0 s et définissez chaque colonne contenant un 0 à tous les 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 Microsoft m’a dit qu’il y avait une solution qui n’implique pas de mémoire supplémentaire, juste deux variables booléennes et une passe, donc je cherche cette réponse.

BTW, imaginez que c’est une masortingce de bits, donc seulement 1 et 0 sont autorisés à être dans la masortingce.

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

J’utilise la première colonne et la première ligne en tant que marqueurs pour savoir où se trouvent les lignes / colonnes avec seulement 1. Ensuite, il y a 2 variables l et c à retenir si 1ère ligne / colonne sont toutes des 1 également. Ainsi, la première passe définit les marqueurs et réinitialise le rest à 0.

Le deuxième passage définit 1 dans les 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 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) 

Cela ne peut pas être fait en un seul passage car un seul bit a un effet sur les bits avant et après dans un ordre quelconque. IOW Quel que soit l’ordre dans lequel vous traversez le tableau, vous pouvez rencontrer 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 un passage. Eh bien c’est a) manquer le point et b) pas la question originale. Je ne posterais pas de question sur le sorting et j’attendrais une réponse qui commence par “en supposant que vous ne voulez sortinger 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 ressortingction.

Donc, mon idée est 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 Zig Zag, parcourez toute la masortingce SAUF la dernière ligne / colonne. A chaque élément, vous définissez la valeur dans la dernière ligne / colonne quant à la logique ET de lui-même avec la valeur de l’élément en cours. En d’autres termes, si vous tapez un 0, la dernière ligne / colonne sera définie sur 0. Si vous avez un 1, la valeur dans 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 1ssi la colonne / ligne correspondante est remplie avec 1s.

Faites un balayage linéaire à travers la dernière ligne et la dernière colonne et cherchez les 1. Définissez 1 dans les éléments correspondants dans le corps de la masortingce où la dernière ligne et la dernière colonne sont les 1.

Le codage, il sera difficile d’éviter les erreurs, mais il devrait fonctionner en une seule fois.

J’ai une solution ici, elle s’exécute en un seul passage et effectue tout le traitement “in place” sans mémoire supplémentaire (sauf pour la croissance de la stack).

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

 #include  /** * 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 masortingx 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 processMasortingx(); void processCorner( int cornerIndex ); bool checkRow( int rowIndex ); bool checkCol( int colIndex ); void zeroRow( int rowIndex ); void zeroCol( int colIndex ); void printMasortingx(); // This function primes the pump void processMasortingx() { 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 masortingx 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 

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 de la même colonne. Donc, vous devez les vérifier et s’il y a un zéro, retournez au premier carré et changez sa valeur à zéro. Je recommande de le faire en deux étapes: la première passe recueille 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 seconde 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 données par vous rendent le problème insoluble.

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

 bool masortingx[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

sauvegarder la masortingce 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, imprimez toutes les valeurs comme 0 pour les valeurs de i et j enregistrées dans a et b les valeurs restantes sont 1, c’est-à-dire (3,3) (3,4) (5,3) et (5,4)

Une autre solution qui nécessite deux passes consiste à accumuler les AND 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 dynamic , en utilisant éventuellement ces deux booléens comme un nombre à 2 bits, mais je n’ai pas encore réussi.

Pouvez-vous s’il vous plait revérifier la déclaration de problème avec votre ingénieur et nous le faire savoir? S’il existe effectivement une solution, je veux continuer à résoudre le problème.

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

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

Si une ligne est quelque chose, mais c’est un 0. Vous pouvez tout faire en une seule fois. Psuedo-code:

 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 un seul passage – mais il y a une supposition ici que N est suffisamment petit pour que le processeur fasse l’arithmétique sur une seule ligne, sinon vous devrez faire une boucle sur chaque ligne pour déterminer si tout est fait Je crois ou non. Mais étant donné que vous posez des questions sur les algos et que je ne limite pas mon matériel, je commencerai simplement par “Construire un processeur qui supporte 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 les valeurs sockets ensemble représentent le tableau et que p et numproduct sont mes iterators et que les variables de produit AND sont utilisées pour implémenter le problème. (J’aurais pu faire une boucle avec l’arithmétique du pointeur 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; } 

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 stacks en C sortingchent (je vous suggère que ce n’est pas le cas, car je devrais pouvoir stocker la masortingce de la manière qui me plait):

  

Est-ce que je manque quelque chose?

Beau challange. Ce type de solution n’utilise que deux booléens créés sur la stack, mais les booléens sont créés plusieurs fois sur la stack 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 

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 ensuite, changer les valeurs de ce motif lors du 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 supplémentaire pour le stockage de travail.
  • n’utilise aucune récursivité.
  • une seule passe de N, pas même N * N.
  • travaillera pour d’autres valeurs de N mais aura besoin de nouveaux #defines.
 #include  #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.-à-d. Ne pas les restaurer, cela peut facilement être fait en un seul passage. Le problème survient lorsque vous essayez de modifier le tableau lorsque vous exécutez l’algorithme).

Voici ma solution Il s’agit simplement d’AND des lignes / colonnes pour un élément de givein (i, j) et de l’imprimer.

 #include  #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 masortingce 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é concensortingque de la masortingce
  2. Stockez-le dans ses cellules d’angle (je les ai stockées dans le sens contraire des aiguilles d’une montre)
  3. Deux variables bool sont utilisées pour conserver les valeurs de deux coins lors de l’évaluation d’un carré particulier.
  4. Ce processus se terminerait lorsque la boucle externe (i) est à mi-chemin.
  5. Évaluer les résultats d’autres cellules basées sur les cellules de coin (pour le rest de i). Ignorez les cellules de coin pendant ce processus.
  6. Lorsque j’atteins n, toutes les cellules auront leur résultat, à l’exception des cellules de coin.
  7. Mettez à jour les cellules de coin. Ceci est une itération supplémentaire à la longueur de n / 2 autre que la contrainte de passage unique mentionnée dans le problème.

Code:

 void Evaluate(bool [,] masortingx, 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; } } } } 

Bien que cela soit impossible compte tenu des contraintes, le moyen le plus efficace de le faire est de parcourir la masortingce en alternant les lignes et les colonnes, ce qui créerait un motif similaire à la pose de briques en zigzag:

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

|-

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

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

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

À la fin de la première passe, la masortingce de résultats aura la bonne réponse.

Semble assez simple. Y a-t-il un truc qui me manque? Vous n’êtes pas autorisé à utiliser un jeu de résultats?

MODIFIER:

Ressemble à une fonction F #, mais cela sortingche un peu car même si vous faites un seul passage, la fonction peut être récursive.

Il semblerait que l’intervieweur essaie de déterminer si vous connaissez la functional programming.

Eh bien, je suis arrivé avec une solution en un seul passage, en place (non récursif) utilisant 4 bools 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 cela devrait être O (N ^ 2) c’est-à-dire. linéaire dans la taille du tableau.

Il m’a fallu quelques heures pour résoudre ce problème – je ne voudrais pas avoir à le faire 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 le “passage unique” comme faisant un balayage dans la masortingce, plutôt que de toucher chaque valeur une fois! 🙂

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

i hope you enjoy my 1-pass c# solution

you can resortingeve an element with O(1) and only need the space of one row and one column of the masortingx

 bool[][] masortingx = { 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 = masortingx.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 pass, 2 booleans. I just have to assume the integer indexes in the iterations don’t count.

This is not a complete solution but I can’t get pass this point.

If I could only determine if a 0 is an original 0 or a 1 that was converted to a 0 then I wouldn’t have to use -1’s and this would work.

My output is like this:

 -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 

The originality of my approach is using the first half of the examination of a row or column to determine if it contains a 0 and the last half to set the values – this is done by looking at x and width-x and then y and height-y in each iteration. Based on the results of the first half of the iteration, if a 0 in the row or column was found, I use the last half of the iteration to change the 1’s to -1’s.

I just realized this could be done with only 1 boolean leaving 1 to …?

I’m posting this hoping someone might say, “Ah, just do this…” (And I spent way too much time on it not to post.)

Here’s the 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 

No one is using binary forms? since it’s only 1 and 0. We can use binary vectors.

 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, eg, 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 

Here’s the 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 

You can do something like this to use one pass but an input and output masortingx:

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

where col(xy) is the bits in the column containing the point xy ; row(xy) is the bits in the row containing the point xy . n is the size of the masortingx.

Then just loop over the input. Possibly expandable to be more space efficient?

One masortingx scan, two booleans, no recursion.

How to avoid the second pass? The second pass is needed to clear the rows or columns when the zero appeares at their end.

However this problem can be solved, because when we scan row #i we already know the row status for the row #i-1. So, while we are scanning the row #i we can simultaneously clear the row #i-1 if it is needed.

The same solution works for columns, but we need to scan rows and columns simultaneously while the data is not changed by the next iteration.

Two booleans are required to store the status of first row and first column, because their values will be changed during the execution of main part of the algorithm.

To avoid adding more booleans we are storing the “clear” flag for the rows and columns in the first row and column of the masortingx.

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

seems like the following works with no additional space requirements:

first note that multiplying the elements of the row times the elements of the line in which an element is, gives the desired value.

In order not to use any additional space (not making a new masortingx and filling it up but instead apply changes to the masortingx directly), start top left of the masortingx and do the computation for any ixi masortingx (that “starts” at (0,0)) before considering any element with any index > i.

hope this works (havent testet)

This is TESTED for different N in C++, and is:
ONE PASS , TWO BOOLS , NO RECURSION , NO EXTRA MEMORY , HOLDS FOR ARBITRARLY LARGE N
(So far none of the solutions here do ALL of these.)

More specifically, I’m amusing two loop counters are okay. I have two const unsigneds, which only exist rather than being computed every time for readability. The outer loop’s interval is [0, N], and the inner loop’s interval is [1, n – 1]. The switch statement is in the loop mostly exists to show very clearly that it really is just one pass.

Algorithm Strategy:

The first sortingck is to us a row and a column from the masortingx itself to accumulate the content of the masortingx, this memory becomes available by offloading all we really need to know from the first row and column into two booleans. The second sortingck is to get two passes out of one, by using the symmetry of the sub-masortingx and its indices.

Algorithm Synopsis:

  • Scan the first row and store if they are all ones in a boolean, do the same for the first column storing the result in a second boolean.
  • For the sub-masortingx excluding the first row and the first column: iterate through, left to right, top to bottom, as one would read a paragraph. Upon visiting each element, also visit the corresponding element that would be visited if visiting the sub-masortingx in reverse. For each element visited AND its value into the where its row crosses the first column, and also AND its value into where its column crosses the first row.
  • Once the center of the sub-masortingx is reached, continue to visit the two elements simultaneously as above. However now set the visited elements’ value to the AND of where its row crosses the first column, and of where its column crosses the first row. After this, the sub-masortingx is complete.
  • Use the two boolean variables computed at the begging to set the first row, and the first column to their correct values.

Templatized C++ Implementation:

 template 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, I realize that it isn’t quite a match, but I got it in one pass using a bool and a byte instead of two bools… close. I also wouldn’t vouch for the efficiency of it but these types of questions often require less than optimal solutions.

 private static void doIt(byte[,] masortingx) { 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) { masortingx[row, col] = 0; } // Force the row to zero if (zeroRow) { masortingx[row, col] = 0; } } } } 

You can sorta do it in one pass — if you don’t count accessing the masortingx in random-access order, which eliminates the benefits of doing it single-pass in the first place (cache-coherence/memory-bandwidth).

[edit: simple, but wrong solution deleted]

You should get better performance than any single-pass method by doing it in two passes: one to accumulate row/column info, and one to apply it. The array (in row-major order) is accessed coherently; for arrays exceeding the cache size (but whose rows can fit in cache), data should be read from memory twice, and stored once:

 void fixmasortingx2(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; } } } 

The simplest solution I can think of is pasted below. The logic is to record which row and column to set zero while iterating.

 import java.util.HashSet; import java.util.Set; public class MasortingxExamples { public static void zeroOut(int[][] myArray) { Set rowsToZero = new HashSet<>(); Set 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); } } 

Here is my Ruby implementation with the the test included, This would take O(MN) space. If we want a real time update (like to show the results when we find zeros rather than waiting the first loop of finding zeros) we can just create another class variable like @output and whenever we find a zero we update @output and not @input .

 require "spec_helper" class Masortingx 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 

The code below creates a masortingx of size m,n. First decide the dimensions of the masortingx. I wanted to fill the masortingx[m][n] with randomly with numbers between 0..10. Then create another masortingx of the same dimensions and fill it with -1s (final masortingx). Then iterate through the initial masortingx to see if you will hit 0. When you hit on location(x,y), go to the final masortingx and fill the row x with 0s and column y with 0s. At the end read through the final masortingx, if the value is -1 (original value) copy the value in the same location of the initial masortingx to final.

 public static void main(Ssortingng[] args) { int m = 5; int n = 4; int[][] masortingxInitial = initMasortingx(m, n); // 5x4 masortingx init randomly int[][] masortingxFinal = masortingxNull(masortingxInitial, 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 zeroRowList = new ArrayList<>(); // Store rows with 0 List 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; } 

here is my solution. As you can see from the code, given a M * N masortingx, it sets the entire row to zero once it inspects a zero in that row.the time complexity of my solution is O(M * N) . I am sharing the whole class which has a static populated array for testing and a display array method to see the result in the 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(Ssortingng[] args) { displayArr(EntireRowSetToZero.arr, 3, 4); setRowToZero(EntireRowSetToZero.arr); System.out.println("--------------"); displayArr(EntireRowSetToZero.arr, 3, 4); } static int[][] setRowToZero(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { if(arr[i][j]==0){ arr[i]=new int[arr[i].length]; } } } return arr; } static void displayArr(int[][] arr, int n, int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { System.out.print(arr[i][j] + " "); } System.out.println(""); } } 

}

One Pass – I have traversed the input only once but used a new array and only two extra Boolean variables.

 public static void main(Ssortingng[] 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(); }