Установите для каждой ячейки матрицы значение 0, если эта строка или столбец содержит 0
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Дана матрица NxN с 0s и 1s.Установите каждую строку, содержащую 0 для всех 0s и установите каждый столбец, содержащий 0 для всех 0s.
Например
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
приводит к
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
Инженер Microsoft сказал мне, что есть решение, которое не требует дополнительной памяти, только две логические переменные и один проход, поэтому я ищу этот ответ.
Кстати, представьте, что это битовая матрица, поэтому в матрице могут быть только единицы и 0.
Решение
Хорошо, я устала, так как сейчас 3 часа ночи, но у меня есть первая попытка на месте с ровно 2 проходами на каждое число в матрице, поэтому в O (NxN) она линейна по размеру матрицы.
Я использую 1-й столбец и первую строку в качестве маркеров, чтобы знать, где строки / столбцы только с 1. Затем есть 2 переменные l и c, которые нужно запомнить, если 1-я строка / столбец тоже все 1. Таким образом, первый проход устанавливает маркеры и сбрасывает остальные на 0.
Второй проход устанавливает 1 в местах, где строки и столбцы помечены как 1, и сбрасывает 1-ю строку / столбец в зависимости от l и c.
Я сильно сомневаюсь, что я могу сделать это за 1 проход, так как квадраты в начале зависят от квадратов в конце. Может быть, мой второй проход можно сделать более эффективным ...
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)
Другие советы
Этого нельзя сделать за один проход, поскольку один бит влияет на биты до и после него в любом порядке. IOW. В каком бы порядке вы ни проходили массив, позже вы можете встретить 0, что означает, что вы должны вернуться назад и изменить предыдущее 1 на 0.
Update
Люди, кажется, думают, что, ограничив N некоторым фиксированным значением (скажем, 8), вы можете решить, что это один проход. Ну, это а) упущение и б) не оригинальный вопрос. Я бы не стал публиковать вопрос о сортировке и ожидать ответа, который начал & Quot; при условии, что вы хотите отсортировать только 8 вещей ... & Quot;.
Тем не менее, это разумный подход, если вы знаете, что N на самом деле ограничено 8. Мой ответ выше отвечает на первоначальный вопрос, который не имеет такого отступления.
Поэтому я предлагаю использовать значения в последней строке / столбце в качестве флага, чтобы указать, все ли значения в соответствующем столбце / строке равны 1 с.
Использование сканирования Zig Zag через всю матрицу, КРОМЕ последняя строка / столбец. В каждом элементе вы устанавливаете значение в последней строке / столбце как логическое И для самого себя со значением в текущем элементе. Другими словами, если вы нажмете 0, последняя строка / столбец будет установлен на 0. Если вы это 1, значение в последней строке / столбце будет 1, только если оно уже было 1. В любом случае установите текущий элемент равным 0.
Когда вы закончите, ваша последняя строка / столбец должна иметь 1 с, если соответствующий столбец / строка была заполнена 1 с.
Выполните линейное сканирование последней строки и столбца и найдите 1 с. Установите 1 в соответствующие элементы в теле матрицы, где последняя строка и столбец равны 1 с.
Кодирование будет непростым, чтобы избежать случайных ошибок и т. д., но это должно работать за один проход.
У меня есть решение, оно выполняется за один проход и выполняет всю обработку " на месте " без дополнительной памяти (за исключением увеличения стека).
Он использует рекурсию, чтобы задержать запись нулей, что, конечно, разрушило бы матрицу для других строк и столбцов:
#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();
}
Я не думаю, что это выполнимо. Когда вы находитесь на первом квадрате и его значение равно 1, у вас нет возможности узнать, каковы значения других квадратов в той же строке и столбце. Таким образом, вы должны проверить их, и если есть ноль, вернитесь к первому квадрату и измените его значение на ноль. Я рекомендую сделать это в два прохода - первый проход собирает информацию о том, какие строки и столбцы должны быть обнулены (информация хранится в массиве, поэтому мы используем некоторую дополнительную память). Второй проход меняет значения. Я знаю, что это не то решение, которое вы ищете, но я думаю, что это практическое решение. Заданные вами ограничения делают проблему неразрешимой.
Я могу сделать это с двумя целочисленными переменными и двумя проходами (до 32 строк и столбцов ...)
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));
проблема может быть решена за один проход
сохранение матрицы в массиве 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 .
теперь выведите все значения как 0 для значений i и j, сохраненных в a и b остальные значения равны 1, т.е. (3,3) (3,4) (5,3) и (5,4)
Другое решение, которое занимает два прохода, заключается в накоплении AND по горизонтали и вертикали:
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
Я думал, что смогу разработать такой алгоритм, используя биты четности , коды Хемминга или динамическое программирование , возможно, с использованием этих двух логических значений в качестве 2-битного числа, но я пока не добился успеха.
Не могли бы вы еще раз проверить формулировку проблемы у своего инженера и сообщить нам об этом? Если действительно есть решение, и я хочу продолжать разбираться с проблемой.
Сохраняйте единственную переменную, чтобы отслеживать, каковы все строки AND, вместе взятые.
Если строка равна -1 (все 1 с), то сделайте следующую строку ссылкой на эту переменную
Если строка ничего, кроме, это 0. Это можно сделать за один проход. Псевдопользователей-код:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
Это должно быть сделано за один проход - но здесь есть предположение, что N достаточно мало, чтобы процессор выполнял арифметику в одной строке, иначе вам придется перебирать каждую строку, чтобы определить если это все 1 или нет, я верю. Но учитывая, что вы спрашиваете об алгоритмах и не ограничиваете мое оборудование, я бы просто начал свой ответ с & Quot; Создать процессор, который поддерживает N-битную арифметику ... & Quot;
Вот один пример того, как это можно сделать на C. Примечание. Я утверждаю, что значения и arr, взятые вместе, представляют массив, а p и numproduct - это мои итераторы и переменные продукта AND, используемые для реализации проблемы. (Я мог зациклить arr с арифметикой указателя, чтобы проверить мою работу, но одного раза было достаточно!)
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;
}
Это дает 0, 0, 6, 0, 6, что является результатом для заданных входных данных.
Или в PHP, если люди думают, что мои стековые игры в C обманывают (я полагаю, что это не так, потому что я должен иметь возможность хранить матрицу любым удобным для меня способом):
<?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);
Я что-то упустил?
Хороший вызов.Это решение использует только два логических значения, созданных в стеке, но логические значения создаются в стеке несколько раз, поскольку функция рекурсивна.
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;
}
Это сканирует по шаблону, подобному:
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
и так далее
А затем меняем значения в этом шаблоне при возврате каждой из функций сканирования.(Снизу вверх):
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
и так далее
Хорошо, это решение, которое
- использует только одно дополнительное длинное значение для рабочего хранилища.
- не использует рекурсию.
- один проход всего N, даже не N * N.
- будет работать для других значений N, но потребуется новый #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;
}
На самом деле.Если вы просто хотите запустить алгоритм и распечатать результаты (т.е.если не восстанавливать их, то это легко можно сделать за один проход.Проблема возникает, когда вы пытаетесь изменить массив во время выполнения алгоритма.
Вот мое решение, оно просто включает в себя определение значений строк / столбцов для элемента givein (i, j) и его распечатку.
#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;
}
}
Я попытался решить эту проблему на C #.
Я использовал две переменные цикла (i и j) отдельно от фактической матрицы и n, представляющих ее размерность
Логика, которую я попробовал, заключается в том, чтобы:
- Вычислите AND для строк и столбцов, входящих в каждый концентрический квадрат матрицы
- Храните его в угловых ячейках (я сохранил их в порядке против часовой стрелки).
- Две переменные bool используются для сохранения значений двух углов при вычислении определенного квадрата.
- Этот процесс завершится, когда внешний цикл (i) будет на полпути.
- Оцените результаты других ячеек на основе угловых ячеек (для остальной части i).Пропустите угловые ячейки во время этого процесса.
- Когда я достигну n, все ячейки получат свой результат, за исключением угловых ячеек.
- Обновите угловые ячейки.Это дополнительная итерация длиной n / 2, отличная от ограничения на один проход, упомянутого в задаче.
Код:
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;
}
}
}
}
Хотя это невозможно, учитывая ограничения, наиболее эффективный способ сделать это - обойти матрицу в виде чередующейся чередующейся строки / столбца, что сделало бы шаблон похожим на укладку кирпичей зигзагообразным способом:
-----
|----
||---
|||--
||||-
Используя это, вы будете входить в каждую строку / столбец, как указано, и, если в любой момент вы встретите 0, установите логическую переменную и повторно пройдете по этой строке / столбцу, установив для записей значение 0 по мере продвижения. .
Это не потребует дополнительной памяти и будет использовать только одну логическую переменную. К сожалению, если & Quot; far & Quot; Все ребра равны 0, это наихудший случай, и вы дважды пройдете весь массив.
создайте результирующую матрицу и установите для всех значений значение 1.пройдите по матрице данных, как только встретится 0, установите для столбца строки результирующей матрицы значение 0
В конце первого прохода результирующая матрица будет содержать правильный ответ.
Выглядит довольно просто.Есть ли какой-то трюк, которого мне не хватает?Вам не разрешено использовать результирующий набор?
Редактировать:
Похоже на функцию F #, но это немного обманывает, поскольку, даже если вы выполняете один проход, функция может быть рекурсивной.
Похоже, интервьюер пытается выяснить, знакомы ли вы с функциональным программированием.
Ну, я придумал однопроходное (нерекурсивное) решение на месте, используя 4 bools и 2 счетчика цикла. Мне не удалось уменьшить его до 2 bools и 2 int, но я не удивлюсь, если бы это было возможно. Это делает приблизительно 3 чтения и 3 записи каждой ячейки, и это должно быть O (N ^ 2) т.е. линейный по размеру массива.
Мне потребовалось пару часов, чтобы разобраться в этом - я бы не хотел придумывать это под давлением интервью! Если я сделал буфу, я слишком устал, чтобы заметить это ...
Гм ... Я хочу определить " однопроходный " как сделать один проход по матрице, а не касаться каждого значения один раз! : -)
#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;
}
Надеюсь, вам понравится мое 1-проходное решение c #
вы можете получить элемент с O (1) и нужно только пространство одной строки и одного столбца матрицы
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 проход, 2 логических значения. Я просто должен предположить, что целочисленные индексы в итерациях не учитываются.
Это не полное решение, но я не могу пройти этот пункт.
Если бы я мог только определить, является ли 0 исходным 0 или 1, преобразованным в 0, я бы не использовал -1, и это сработало бы.
Мой вывод такой:
-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
Оригинальность моего подхода заключается в использовании первой половины проверки строки или столбца, чтобы определить, содержит ли она 0, а в последней половине - для установки значений - это делается путем просмотра x и width-x, а затем y и height-y в каждой итерации. Исходя из результатов первой половины итерации, если в строке или столбце был найден 0, я использую последнюю половину итерации, чтобы изменить 1 на -1.
Я только что понял, что это можно сделать только с одним логическим значением, оставляя 1 для ...?
Я публикую это в надежде, что кто-то скажет: "! Просто сделайте это ... " (И я потратил слишком много времени на это, чтобы не писать.)
Вот код в 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
Никто не использует двоичные формы? так как это только 1 и 0. Мы можем использовать двоичные векторы.
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
Вот тест:
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)
И вывод:
Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
Вы можете сделать что-то подобное, чтобы использовать один проход, но матрицу ввода и вывода:
output(x,y) = col(xy) & row(xy) == 2^n
где col(xy) - биты в столбце, содержащем точку xy; row(xy) - это биты в строке, содержащей точку n. <=> - это размер матрицы.
Тогда просто зациклите ввод. Возможно расширяемый, чтобы быть более экономичным?
Одно матричное сканирование, два логических значения, без рекурсии.
Как избежать второго прохода? Второй проход необходим для очистки строк или столбцов, когда на их конце появляется ноль.
Однако эту проблему можно решить, потому что, когда мы сканируем строку #i, мы уже знаем статус строки для строки # i-1. Поэтому, пока мы сканируем строку #i, мы можем одновременно очистить строку # i-1, если это необходимо.
То же решение работает для столбцов, но нам нужно сканировать строки и столбцы одновременно, пока данные не изменятся при следующей итерации.
Два логических значения требуются для хранения состояния первой строки и первого столбца, поскольку их значения будут изменены во время выполнения основной части алгоритма.
Чтобы не добавлять больше логических значений, мы храним " clear " флаг для строк и столбцов в первой строке и столбце матрицы.
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();
}
похоже, что следующие работы без дополнительных требований к пространству:
сначала обратите внимание, что умножение элементов строки на элементы строки, в которой находится элемент, дает желаемое значение.
Чтобы не использовать дополнительное пространство (не создавая новую матрицу и не заполняя ее, а применяя изменения непосредственно к матрице), начните с левого верхнего угла матрицы и выполните вычисления для любой матрицы ixi (которая " начинает " с (0,0)) перед рассмотрением любого элемента с любым индексом > я.
надеюсь, что это сработает (еще нет)
Это ПРОВЕРЕННЫЙ для разных N в C ++, и это:
ОДИН ПРОХОД, ДВА БУЛА, НИКАКОЙ РЕКУРСИИ, НЕТ ДОПОЛНИТЕЛЬНОЙ ПАМЯТИ, СПРАВЕДЛИВО ДЛЯ СКОЛЬ УГОДНО БОЛЬШИХ N
(Пока что ни одно из приведенных здесь решений не выполняет ВСЕГО этого.)
Более конкретно, я забавляюсь, что два счетчика циклов в порядке.У меня есть два константы без знака, которые только существуют, а не вычисляются каждый раз для удобства чтения.Интервал внешнего цикла равен [0, N], а интервал внутреннего цикла равен [1, n - 1].Оператор switch находится в цикле, который в основном существует для того, чтобы очень четко показать, что на самом деле это всего лишь один проход.
Алгоритм Стратегии:
Первый трюк заключается в том, чтобы использовать строку и столбец из самой матрицы для накопления содержимого матрицы, эта память становится доступной путем выгрузки всего, что нам действительно нужно знать из первой строки и столбца, в два логических значения.Второй трюк заключается в том, чтобы получить два прохода из одного, используя симметрию подматрицы и ее индексов.
Краткий обзор алгоритма:
- Просканируйте первую строку и сохраните, если все они находятся в логическом значении, сделайте то же самое для первого столбца, сохранив результат во втором логическом значении.
- Для подматрицы, исключающей первую строку и первый столбец:повторите слева направо, сверху вниз, как при чтении абзаца.После посещения каждого элемента также посетите соответствующий элемент, который был бы посещен при обратном посещении подматрицы.Для каждого посещенного элемента И его значения в поле, где его строка пересекает первый столбец, а также И его значения в поле, где его столбец пересекает первую строку.
- Как только вы достигнете центра субматрицы, продолжайте посещать два элемента одновременно, как описано выше.Однако теперь установите значение посещенных элементов равным И того, где его строка пересекает первый столбец, и того, где его столбец пересекает первую строку.После этого субматрица завершена.
- Используйте две логические переменные, вычисленные в начале, чтобы присвоить первой строке и первому столбцу правильные значения.
Шаблонная реализация на C ++:
template<unsigned n>
void SidewaysAndRowColumn(int((&m)[n])[n]) {
bool fcol = m[0][0] ? true : false;
bool frow = m[0][0] ? true : false;
for (unsigned d = 0; d <= n; ++d) {
for (unsigned i = 1; i < n; ++i) {
switch (d) {
case 0:
frow = frow && m[d][i];
fcol = fcol && m[i][d];
break;
default:
{
unsigned const rd = n - d;
unsigned const ri = n - i;
if (d * n + i < rd * n + ri)
{
m[ d][ 0] &= m[ d][ i];
m[ 0][ d] &= m[ i][ d];
m[ 0][ i] &= m[ d][ i];
m[ i][ 0] &= m[ i][ d];
m[rd][ 0] &= m[rd][ri];
m[ 0][rd] &= m[ri][rd];
m[ 0][ri] &= m[rd][ri];
m[ri][ 0] &= m[ri][rd];
}
else
{
m[ d][ i] = m[ d][0] & m[0][ i];
m[rd][ri] = m[rd][0] & m[0][ri];
}
break;
}
case n:
if (!frow)
m[0][i] = 0;
if (!fcol)
m[i][0] = 0;
};
}
}
m[0][0] = (frow && fcol) ? 1 : 0;
}
Хорошо, я понимаю, что это не совсем совпадает, но я получил его за один проход, используя bool и байт вместо двух bool ... close. Я бы также не ручался за его эффективность, но такие вопросы часто требуют неоптимальных решений.
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; }
}
}
}
Вы можете сделать это за один проход - если вы не учитываете доступ к матрице в порядке произвольного доступа, что исключает преимущества выполнения этого за один проход в первую очередь (cache-coherence / memory-bandwidth) ).
[edit: простое, но неправильное решение удалено]
Вы должны получить лучшую производительность, чем любой однопроходный метод, выполнив его в два этапа: один для накопления информации о строке / столбце и один для ее применения. Доступ к массиву (в порядке следования строк) связан; для массивов, превышающих размер кеша (но строки которых могут уместиться в кеше), данные должны считываться из памяти дважды и сохраняться один раз:
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;
}
}
}
Самое простое решение, которое я могу придумать, вставлено ниже. Логика заключается в том, чтобы записать, какую строку и столбец установить на ноль во время итерации.
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);
}
}
Вот моя реализация Ruby с включенным тестом. Это заняло бы пространство O (MN). Если нам нужно обновление в режиме реального времени (например, показ результатов, когда мы находим нули, а не ожидание первого цикла нахождения нулей), мы можем просто создать другую переменную класса, например @output, и всякий раз, когда мы находим ноль, мы обновляем @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
Приведенный ниже код создает матрицу размером m, n. Сначала определитесь с размерами матрицы. Я хотел заполнить матрицу [m] [n] случайным образом числами от 0,10. Затем создайте другую матрицу с такими же размерами и заполните ее -1 с (окончательная матрица). Затем выполните итерацию по начальной матрице, чтобы увидеть, достигнете ли вы 0. Когда вы нажмете на местоположение (x, y), перейдите к финальной матрице и заполните строку x 0 и столбец y 0. В конце прочитайте окончательную матрицу, если значение равно -1 (исходное значение), скопируйте значение в том же месте исходной матрицы в конечную.
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;
}
вот мое решение.Как вы можете видеть из кода, учитывая матрицу M * N, она устанавливает всю строку равной нулю, как только проверяет ноль в этой строке. временная сложность моего решения равна O (M * N) .Я делюсь всем классом, у которого есть статический заполненный массив для тестирования и метод display array, чтобы увидеть результат в консоли.
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("");
}
}
}
Один проход - я обошел ввод только один раз, но использовал новый массив и только две дополнительные логические переменные.
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();
}
