Définissez chaque cellule de la matrice sur 0 si cette ligne ou cette colonne contient un 0
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné une matrice NxN avec des 0 et des 1. Définissez chaque ligne contenant un 0 sur tous les 0 et définissez toutes les colonnes contenant un 0 sur 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ésultats dans
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 ne nécessitant pas de mémoire supplémentaire, à savoir deux variables booléennes et un seul passage. Je recherche donc cette réponse.
BTW, imaginez que ce soit une matrice de bits, donc seuls 1 et 0 permettent de figurer dans la matrice.
La solution
Ok, donc je suis fatigué car il est 3 heures du matin ici, mais j’ai un premier essai sur place avec exactement 2 passages sur chaque nombre de la matrice, donc en O (NxN) et il 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ù sont les lignes / colonnes avec seulement 1. Ensuite, il y a 2 variables l et c à retenir si la 1ère rangée / colonne est également égale à 1. Donc, la première passe définit les marqueurs et réinitialise le reste à 0.
La deuxième passe définit 1 aux emplacements où les lignes et les colonnes étaient marquées comme étant 1 et réinitialise la 1ère ligne / col en fonction de l et de c.
Je doute fortement que je puisse être fait en 1 seul passage car les carrés au début dépendent des carrés à la fin. Peut-être que ma deuxième passe pourrait ê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)
Autres conseils
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 parcourez 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 seul passage. Eh bien, c’est a) rater le point et b) pas la question initiale. Je ne publierais pas de question sur le tri et espérerais une réponse qui commencerait "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’existe pas de telle restriction.
Mon idée est donc d'utiliser les valeurs de la dernière ligne / colonne en tant qu'indicateur pour indiquer si toutes les valeurs de la colonne / ligne correspondante sont égales à 1.
Utilisation d'un balayage de Zig Zag à travers la matrice entière EXCEPT la dernière ligne / colonne. À chaque élément, vous définissez la valeur dans la dernière ligne / colonne en tant qu'ET logique de lui-même avec la valeur de l'élément en cours. En d’autres termes, si vous appuyez sur un 0, la dernière ligne / colonne sera définie sur 0. Si vous le définissez sur 1, la valeur de la dernière ligne / colonne ne sera 1 que si elle était déjà 1. Dans tous les cas, définissez l'élément en cours sur 0.
Une fois que vous avez terminé, votre dernière ligne / colonne devrait comporter 1s si et seulement si la colonne / ligne correspondante était remplie par 1.
Faites un balayage linéaire à travers la dernière ligne et colonne et recherchez les 1. Définissez les 1 dans les éléments correspondants du corps de la matrice, où la dernière ligne et la dernière colonne sont des 1.
Il sera difficile de coder pour éviter les erreurs non-récurrentes, etc., mais cela devrait fonctionner en un seul passage.
J'ai une solution ici, elle s'exécute en un seul passage et effectue tous les traitements "en place". sans mémoire supplémentaire (sauf pour agrandir la pile).
Il utilise la récursivité pour retarder l'écriture de zéros, ce qui détruirait bien sûr la matrice des 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();
}
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 vérifier ceux-ci et s'il y a un zéro, retourner à la première case et changer sa valeur à zéro. Je vous 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 seconde passe change 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 fournies 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 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
enregistrement 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 .
affiche maintenant toutes les valeurs à 0 pour les valeurs de i et j enregistrées dans a et b les autres valeurs sont 1, à savoir (3,3) (3,4) (5,3) et (5,4)
Une autre solution qui nécessite deux passes consiste à accumuler des ET 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 les bits de parité , Codes Hamming ou programmation dynamique , en utilisant éventuellement ces deux booléens comme un nombre à 2 bits, mais je n'ai pas encore eu de succès.
Pouvez-vous s'il vous plaît vérifier à nouveau la déclaration du problème avec votre ingénieur et nous le faire savoir? Si il y a une solution, je veux continuer à réduire le problème.
Conservez une seule variable pour garder une trace de toutes les lignes AND qui sont ensemble.
Si une ligne a la valeur -1 (tous les 1), alors faites de la ligne suivante une référence à cette variable
Si une ligne est autre chose que 0, c'est 0. Vous pouvez tout faire en un seul passage. Code Psuedo:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
Cela devrait suffire, en un seul passage - mais on suppose ici que N est assez petit pour que le CPU effectue l'arithmétique sur une seule ligne, sinon vous devrez passer en boucle sur chaque ligne pour déterminer si c'est tout 1 ou pas, je crois. Mais étant donné que vous vous posez des questions sur les algues et sur la non-contrainte de mon matériel, je commencerais ma réponse par "Construire un processeur prenant en charge l'arithmétique à N bits ..."
Voici un exemple d'utilisation de C. Remarque: Je soutiens que les valeurs et arr, pris ensemble, représentent le tableau, et p et numproduct sont les variables de mon itérateur et AND utilisées pour implémenter le problème. (J'aurais pu faire une boucle avec arithmétique de pointeur pour valider mon travail, mais une fois suffisait!)
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;
}
Ceci 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 bon me semble):
<?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;
}
Ceci scanne selon un motif tel que:
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
et ainsi de suite
Ensuite, modifiez les valeurs de ce modèle lors de chaque opération de balayage. (Bottom up):
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
et ainsi de suite
D'accord, c'est une solution qui
- utilise une seule valeur extra-longue pour le stockage de travail.
- n'utilise pas de récursivité.
- un seul passage de 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;
}
En fait. Si vous souhaitez simplement exécuter l'algorithme et imprimer les résultats (c'est-à-dire ne pas les restaurer, vous pouvez facilement le faire en un seul passage. Le problème survient lorsque vous essayez de modifier le tableau pendant l'exécution de l'algorithme.
Voici ma solution. Il s’agit simplement d’ajouter 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 plus de la matrice réelle et n représentant sa dimension
La logique que j'ai essayée est de:
- Calculez AND pour les lignes et les colonnes impliquées dans chaque carré concentrique de la matrice
- Stockez-le dans ses cellules d'angle (je les ai stockées dans le sens inverse des aiguilles d'une montre)
- Deux variables booléennes sont utilisées pour conserver les valeurs de deux coins lors de l'évaluation d'un carré particulier.
- Ce processus se terminerait lorsque la boucle extérieure (i) serait à mi-chemin.
- Évaluez les résultats d'autres cellules en fonction des cellules d'angle (pour le reste de i). Ignorer les cellules de coin pendant ce processus.
- Lorsque i atteint n, toutes les cellules ont leur résultat, à l'exception des cellules de coin.
- Mettez à jour les cellules d'angle. Il s’agit d’une itération supplémentaire de longueur 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;
}
}
}
}
Bien que cela soit impossible compte tenu des contraintes, le moyen le plus économe en espace de le faire consiste à parcourir la matrice de manière superposée, alternant ligne / colonne, ce qui créerait un motif similaire à la pose de briques en zigzag:
-----
|----
||---
|||--
||||-
Avec cela, vous iriez dans chaque ligne / colonne, comme indiqué, et si vous rencontrez un 0 à tout moment, définissez une variable booléenne, puis 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 utilisera une seule variable booléenne. Malheureusement, si le " far " bord est défini sur 0, c’est le pire des cas et vous parcourez le tableau en entier deux fois.
créez une matrice de résultats et définissez toutes les valeurs sur 1. parcourez la matrice de données dès qu’un 0 est rencontré, définissez la colonne de rangée de la matrice de résultats sur 0
À la fin du premier passage, la matrice de résultat aura la bonne réponse.
Ça a l'air simple. Y a-t-il un truc qui me manque? N'êtes-vous pas autorisé à utiliser un jeu de résultats?
EDIT:
Ressemble à une fonction F #, mais cela trompe un peu car même si vous effectuez un seul passage, la fonction peut être récursive.
Il semble que l'intervieweur tente de savoir si vous connaissez la programmation fonctionnelle.
Eh bien, j’ai proposé une solution en un seul passage (non récursive) utilisant 4 compteurs et 2 compteurs de boucles. Je n'ai pas réussi à le réduire à 2 bools et 2 ints, mais je ne serais pas surpris si cela était possible. Il fait environ 3 lectures et 3 écritures de chaque cellule, et il devrait être O (N ^ 2) c'est-à-dire. linéaire dans la taille du tableau.
Il m'a fallu quelques heures pour résoudre celui-ci - je ne voudrais pas être obligé de le présenter sous la pression d'une interview! Si j'ai fait un bobo, je suis trop fatigué pour le repérer ...
Euh ... je choisis de définir le terme "passe unique". en faisant un balayage dans 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 en un seul passage c #
vous pouvez récupérer un élément avec O (1) et n’avoir 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 passe, 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 -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 - ceci 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 modifier les 1 en -1.
Je viens de réaliser que cela pourrait être fait avec seulement 1 booléen laissant 1 à ...?
Je publie ce message en espérant que quelqu'un pourrait dire: "Ah, fais ça ..." (Et j’ai passé trop de temps à 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? comme il est seulement 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 en utilisant une passe mais une matrice d'entrée et de sortie:
output(x,y) = col(xy) & row(xy) == 2^n
où col (xy) correspond aux bits de la colonne contenant le point xy ; ligne (xy) correspond aux bits de la ligne contenant le point xy . n est la taille de la matrice.
Ensuite, passez en boucle sur l'entrée. Peut-être extensible pour gagner de la place?
Un balayage matriciel, deux booléens, pas de récursivité.
Comment éviter le second passage? La deuxième passe est nécessaire pour effacer les lignes ou les colonnes lorsque le zéro apparaît à la 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 pour la ligne # i-1. Ainsi, pendant que nous balayons la rangée #i, nous pouvons effacer simultanément la rangée # i-1 si nécessaire.
La même solution fonctionne pour les colonnes, mais nous devons analyser simultanément les lignes et les colonnes sans modifier les données à la prochaine itération.
Deux booléens sont nécessaires pour stocker le statut 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 d’autres booléens, nous stockons le "transparent". indicateur pour les lignes et les colonnes de la première ligne et de la 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 fonctionner comme suit sans espace supplémentaire requis:
notons d’abord que la multiplication des éléments de la ligne par ceux 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 de nouvelle matrice et la remplir, mais appliquer directement les modifications à la matrice), commencez en haut à gauche de la matrice et effectuez le calcul de toute matrice ixi (qui "commence"). ; at (0,0)) avant de considérer un élément avec un index > i.
espérons que cela fonctionne (ne pas avoir testé)
Il s'agit de TESTED pour différents N en C ++, à savoir:
UN PASSE , DEUX BOOLS , PAS DE RÉCURSION , PAS DE MÉMOIRE SUPPLÉMENTAIRE , DES TROT POUR ARBITRARLY GRAND N
(Jusqu'à présent, aucune des solutions ici ne fait TOUTES celles-ci.)
Plus précisément, je m'amuse deux compteurs de boucle, ça va. J'ai deux const non signés, qui n'existent que plutôt que d'être calculés à chaque fois pour des raisons de 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 pour montrer très clairement qu’il s’agit bien d’un seul passage.
Stratégie algorithmique:
La première astuce consiste à nous une rangée 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 de la colonne sur deux booléens. La deuxième astuce consiste à obtenir deux passages sur un, en utilisant la symétrie de la sous-matrice et ses indices.
Synopsis de l'algorithme:
- Parcourez la première ligne et stockez-les s'ils sont tous 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: parcourez, de gauche à droite, de haut en bas, comme si vous lisiez un paragraphe. Lors de la visite de chaque élément, visitez également l'élément correspondant qui serait visité si la sous-matrice était visitée à l'envers. Pour chaque élément visité ET sa valeur dans l'emplacement où sa ligne traverse la première colonne, et aussi sa valeur dans l'emplacement où sa colonne traverse 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 AND de l'endroit où sa ligne traverse la première colonne et de l'endroit où sa colonne traverse la première ligne. Ensuite, la sous-matrice est terminée.
- 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 C ++ modélisée:
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 un match, mais je l'ai eu en une passe en utilisant un bool et un octet au lieu de deux bool ... tout près. Je ne voudrais pas non plus en garantir l'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, vous éviterez tout avantage à le faire en un seul passage (cohérence du cache / bande passante de la 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: un pour accumuler les informations de ligne / colonne et un pour l’appliquer. Le tableau (dans l'ordre des lignes) est accessible de manière cohérente; Pour les baies dépassant la taille du cache (mais dont les lignes peuvent tenir dans le cache), les données doivent être lues deux fois dans la mémoire 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 quelle ligne et quelle colonne définir à 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 un 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 @output et chaque fois que nous trouvons un zéro nous mettons à jour @output et 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 les dimensions de la matrice. Je voulais remplir la matrice [m] [n] avec au hasard avec des nombres compris entre 0..10. Créez ensuite une autre matrice de mêmes dimensions et remplissez-la avec -1s (matrice finale). Parcourez ensuite la matrice initiale pour voir si vous atteindrez 0. Lorsque vous frappez un emplacement (x, y), accédez à la matrice finale et remplissez la ligne x avec 0 et la colonne y avec 0. À la fin, parcourez la matrice finale si la valeur est -1 (valeur originale), copiez-la au même endroit que la matrice initiale dans la version finale.
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 constater d'après le code, dans le cas d'une matrice M * N, la ligne entière est mise à zéro une fois le zéro inséré dans cette ligne. La complexité temporelle de ma solution est O (M * N). Je partage la classe entière qui a un tableau rempli statique à tester et une méthode 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("");
}
}
}
One Pass - J'ai traversé 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();
}
