해당 행이나 열에 0이 포함된 경우 행렬의 모든 셀을 0으로 설정합니다.
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
0과 1로 구성된 NxN 행렬이 주어졌습니다.다음을 포함하는 모든 행을 설정합니다. 0 모든 0s를 포함하는 모든 열을 설정합니다. 0 모든 0에스.
예를 들어
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 엔지니어가 추가 메모리 없이 두 개의 부울 변수와 하나의 패스만 포함하는 솔루션이 있다고 말했기 때문에 저는 그 답을 찾고 있습니다.
그런데, 이것이 비트 매트릭스라고 상상해 보십시오. 따라서 매트릭스에는 1과 0만 허용됩니다.
해결책
좋아, 여기에서 오전 3 시인 것처럼 피곤하지만 매트릭스의 각 숫자에 대해 정확히 2 개의 패스가있는 첫 번째 시도가 있으므로 O (NXN)에서 매트릭스 크기의 선형입니다.
나는 첫 번째 열과 첫 번째 행을 마커로 사용하여 1만의 행/콜이 어디에 있는지 알 수 있습니다. 그런 다음 첫 번째 행/열이 모두 1인지 기억 해야하는 2 개의 변수 L과 C가 있습니다. 따라서 첫 번째 패스는 마커를 설정하고 나머지를 0으로 재설정합니다.
두 번째 패스는 행과 콜이 1으로 표시된 곳에서 1을 설정하고 L과 c에 따라 1 줄/col을 재설정합니다.
처음에 사각형이 결국 사각형에 의존하기 때문에 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)
다른 팁
단일 비트는 주문 전후에 비트에 영향을 미치기 때문에 한 번의 패스로 수행 할 수 없습니다. 배열을 가로 지르는 순서가 무엇이든, 나중에 0을 올릴 수 있습니다.
업데이트
사람들은 n을 일부 고정 값 (예 : 8)으로 제한함으로써 이것을 하나의 패스라고 생각할 수 있다고 생각하는 것 같습니다. 글쎄, 그것은 a) 요점을 놓치고 b) 원래 질문이 아닙니다. 나는 정렬에 대한 질문을 게시하지 않고 "8 가지만 정렬하고 싶다고 가정하면"시작한 답변을 기대합니다.
즉, N이 실제로 8으로 제한된다는 것을 알고 있다면 합리적인 접근법입니다.
그래서 내 생각은 마지막 행/열의 값을 해당 열/행의 모든 값이 1인지 여부를 나타내는 플래그로 사용하는 것입니다.
사용하여 지그재그 스캔 마지막 행/열을 제외한 전체 행렬을 통해.각 요소에서 최종 행/열의 값을 현재 요소의 값과 논리 AND로 설정합니다.즉, 0을 누르면 마지막 행/열이 0으로 설정됩니다.1인 경우 마지막 행/열의 값은 이미 1인 경우에만 1이 됩니다.어쨌든 현재 요소를 0으로 설정합니다.
완료되면 해당 열/행이 1로 채워진 경우 마지막 행/열에 1이 있어야 합니다.
마지막 행과 열을 통해 선형 스캔을 수행하고 1을 찾습니다.마지막 행과 열이 모두 1인 행렬 본문의 해당 요소에 1을 설정합니다.
코딩을 하면 하나씩 오류 등을 방지하는 것이 까다로울 수 있지만 한 번에 작동해야 합니다.
여기에 솔루션이 있고 단일 패스로 실행되며 추가 메모리가없는 "제자리에"모든 처리를 수행합니다 (스택을 성장시키기 위해 저장).
그것은 재귀를 사용하여 0의 글쓰기를 지연시킵니다. 물론 다른 행과 cols의 매트릭스를 파괴 할 것입니다.
#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 일 때, 같은 행과 열의 다른 사각형의 값이 무엇인지 알 방법이 없습니다. 따라서 그것들을 확인해야하고 0이 있으면 첫 번째 정사각형으로 돌아가서 그 값을 0으로 변경하십시오. 첫 번째 패스는 어떤 행과 열을 제로화 해야하는지에 대한 정보를 수집하는 것이 좋습니다 (정보는 배열에 저장되므로 추가 메모리를 사용하고 있음). 두 번째 패스는 값을 변경합니다. 나는 그것이 당신이 찾고있는 솔루션이 아니라는 것을 알고 있지만, 그것이 실용적인 것이라고 생각합니다. 귀하가 제공 한 제약은 문제를 해결할 수 없게 만듭니다.
나는 두 개의 정수 변수와 2 개의 패스 (최대 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 .
이제 a와 b에 저장된 i와 j의 값에 대해 모든 값을 0으로 인쇄합니다. 나머지 값은 1 (3,3) (3,4) (5,3) 및 (5,4)입니다.
또 다른 두 번의 패스를 취하고 수평 및 수직으로 축적되고 다음과 같습니다.
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이 아닌 경우에는 0입니다.한 번의 패스로 모든 것을 할 수 있습니다.유사 코드:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
단일 패스로 그렇게 해야 합니다. 그러나 여기서는 N이 CPU가 단일 행에서 산술을 수행할 수 있을 만큼 작다고 가정합니다. 그렇지 않으면 각 행을 반복하여 전체인지 확인해야 합니다. 1초인지 아닌지 나는 믿습니다.하지만 당신이 알고에 대해 묻고 내 하드웨어를 제한하지 않는다는 점을 고려하면 나는 "N비트 산술을 지원하는 CPU 구축..."으로 대답을 시작하겠습니다.
C에서 이를 수행하는 방법에 대한 한 가지 예는 다음과 같습니다.참고로 나는 값과 arr이 함께 배열을 나타내고, p와 numproduct가 문제를 구현하는 데 사용되는 반복자이자 AND product 변수라고 주장합니다.(내 작업을 검증하기 위해 포인터 산술을 사용하여 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의 다른 값에 대해 작동하지만 새로운 #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;
}
실제로. 알고리즘을 실행하고 결과를 인쇄하려면 결과를 인쇄하려면 (예 : 복원하지 않으면 한 번의 패스로 쉽게 수행 할 수 있습니다. 알고리즘을 실행할 때 배열을 수정하려고 할 때 문제가 발생합니다.
여기에는 내 솔루션이 있습니다. 단지주는 (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#에서이 문제를 해결하려고했습니다.
실제 행렬을 제외하고는 2 개의 루프 변수 (I 및 J)를 사용했으며 차원을 나타내는 N을 사용했습니다.
내가 시도한 논리는 다음과 같습니다.
- 매트릭스의 각 동심 사각형에 관련된 행 및 콜을 계산하고
- 코너 셀에 보관하십시오 (반 시계 방향으로 저장했습니다)
- 특정 사각형을 평가할 때 두 개의 모서리의 값을 유지하는 데 두 개의 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으로 설정하십시오.
추가 메모리가 필요하지 않으며 하나의 부울 변수 만 사용합니다. 불행히도, "먼"가장자리가 모두 0으로 설정되면 최악의 경우이며 전체 배열을 두 번 걷습니다.
결과 매트릭스를 만들고 모든 값을 1으로 설정하십시오. 0이 발생하자마자 데이터 매트릭스를 통과하고 결과 매트릭스 행 열을 0으로 설정하십시오.
첫 번째 패스가 끝나면 결과 행렬에는 정답이 있습니다.
매우 간단 해 보입니다. 내가 놓친 트릭이 있습니까? 결과 세트를 사용할 수 없습니까?
편집하다:
F# 함수처럼 보이지만 단일 패스를 수행하더라도 기능이 재귀적일 수 있으므로 약간의 속임수입니다.
면접관이 기능 프로그래밍을 알고 있는지 알아 내려고하는 것 같습니다.
글쎄, 나는 4 개의 bool과 2 개의 루프 카운터를 사용하여 단일 패스, 현장 (비 수술) 솔루션을 생각해 냈습니다. 나는 그것을 2 부와 2 개의 int로 줄일 수 없었지만 가능하다면 놀라지 않을 것입니다. 그것은 각 셀에 대해 약 3 개의 읽기와 3 개의 쓰기를 수행하며, 즉 (n^2) IE 여야합니다. 배열 크기의 선형.
이것을 퍼즐을 피우는 데 몇 시간이 걸렸습니다 - 나는 인터뷰의 압력으로 그것을 생각해 내고 싶지 않을 것입니다! 내가 booboo를 만들었다면 나는 그것을 발견하기에는 너무 피곤하다 ...
음 ... "단일 패스"를 각 값을 한 번 터치하지 않고 매트릭스를 통해 하나의 스윕으로 정의하기로 결정했습니다! :-)
#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으로 변환 된 원래 0 또는 1인지 결정할 수 있다면 -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 부울만으로도 ... 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) 점을 포함하는 행의 비트입니다 xy. n 매트릭스의 크기입니다.
그런 다음 입력을 통해 루프하십시오. 더 많은 공간 효율성을 높이기 위해 확장 할 수 있습니까?
하나의 매트릭스 스캔, 2 개의 부울, 재귀 없음.
두 번째 패스를 피하는 방법? 제로가 끝에 나타나면 행이나 열을 지우려면 두 번째 패스가 필요합니다.
그러나이 문제를 해결할 수 있습니다. 행 #I를 스캔 할 때 이미 행 #I-1의 행 상태를 알고 있기 때문입니다. 따라서 행을 스캔하는 동안 필요한 경우 행 #I-1을 동시에 지울 수 있습니다.
동일한 솔루션은 열에 대해 작동하지만 다음 반복에 의해 데이터가 변경되지 않고 행과 열을 동시에 스캔해야합니다.
알고리즘의 기본 부분을 실행하는 동안 값이 변경되므로 첫 번째 행 및 첫 열의 상태를 저장해야합니다.
더 많은 부울을 추가하지 않기 위해 행렬의 첫 번째 행과 열에 행과 열에 대한 "명확한"플래그를 저장하고 있습니다.
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)) 지수가있는 요소를 고려하기 전에> i.
이 효과가 있기를 바랍니다 (Havent Test)
이것은 테스트 C ++의 다른 N의 경우, 다음과 같습니다.
하나의 패스, 두 bols, 재귀가 없습니다, 추가 메모리가 없습니다, 임의의 큰 n에 대한 보류
(지금까지 여기에있는 솔루션은이 모든 것을하지 않습니다.)
보다 구체적으로, 나는 두 개의 루프 카운터가 괜찮습니다. 나는 두 개의 const 서명이 있는데, 이는 가독성을 위해 매번 계산하기보다는 존재합니다. 외부 루프의 간격은 [0, n]이고 내부 루프의 간격은 [1, n -1]입니다. 스위치 명령문은 루프에 주로 존재합니다. 실제로 하나의 패스 일뿐임을 명확하게 보여줍니다.
알고리즘 전략 :
첫 번째 요령은 행렬 자체의 행과 열을 행렬의 내용을 축적하여 행렬과 열을 축적하는 것입니다.이 메모리는 첫 번째 행과 열에서 두 부울로 실제로 알아야 할 모든 것을 오프로드하여 사용할 수 있습니다. 두 번째 요령은 서브 매트릭스의 대칭과 그 지수를 사용하여 두 번의 패스를 하나로 꺼내는 것입니다.
알고리즘 시놉시스 :
- 첫 번째 행을 스캔하고 부울에있는 모든 행이있는 경우 저장하고 첫 번째 열에 대해 동일한 작업을 수행하여 결과를 두 번째 부울에 저장하십시오.
- 첫 번째 행과 첫 번째 열을 제외한 하위 매트릭스의 경우, 단락을 읽을 수 있듯이 첫 번째 열과 첫 번째 열 : 반복을 통해 왼쪽에서 오른쪽으로, 위에서 아래로. 각 요소를 방문하면 서브 매트릭스를 방문하면 방문 할 해당 요소도 방문하십시오. 각 요소에 대해 방문하고 그 값은 그 행이 첫 번째 열을 가로 지르는 곳으로, 그리고 그 값은 열이 첫 번째 행을 가로 지르는 위치로 향합니다.
- 하위 매트릭스의 중심에 도달하면 위와 같이 두 요소를 동시에 계속 방문하십시오. 그러나 이제 방문한 요소의 값을 행이 첫 번째 열을 가로 지르는 위치와 열이 첫 번째 행을 가로 지르는 위치로 설정합니다. 그 후, 하위 매트릭스가 완료되었습니다.
- 구매시 계산 된 두 부울 변수를 사용하여 첫 번째 행을 설정하고 첫 번째 열은 올바른 값으로 설정됩니다.
템플릿 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과 Byte를 사용하여 한 번의 패스로 그것을 얻었다. 또한 효율성을 보증하지는 않지만 이러한 유형의 질문은 종종 최적의 솔루션보다 덜 필요합니다.
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; }
}
}
}
무작위 액세스 순서로 매트릭스에 액세스하는 것을 계산하지 않으면 처음에 단일 패스 (캐시 코어 런스/메모리 대역 심)의 이점을 제거 할 수 있습니다.
편집 : 단순하지만 잘못된 솔루션 삭제
두 번의 패스로 수행하여 단일 패스 방법보다 더 나은 성능을 얻어야합니다. 하나는 행/열 정보를 축적하고 하나는 적용 할 수 있습니다. 배열 (행-대기 순서)은 일관되게 액세스됩니다. 캐시 크기를 초과하는 배열의 경우 (캐시에 행이 맞는 행)는 메모리에서 두 번 읽고 한 번 저장해야합니다.
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;
}
}
}
내가 생각할 수있는 가장 간단한 솔루션은 아래에 붙여져 있습니다. 논리는 반복하는 동안 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);
}
}
다음은 테스트가 포함 된 내 루비 구현입니다. 이것은 O (MN) 공간이 필요합니다. 실시간 업데이트를 원한다면 (제로를 찾는 첫 번째 루프를 기다리는 대신 0을 찾을 때 결과를 표시하는 것과 같은) 다른 클래스 변수를 다음과 같은 다른 클래스 변수를 만들 수 있습니다. @output 그리고 우리가 0을 찾을 때마다 우리는 업데이트합니다 @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의 행렬을 만듭니다. 먼저 매트릭스의 치수를 결정하십시오. 나는 0..10 사이의 숫자로 매트릭스 [m] [n]을 무작위로 채우고 싶었다. 그런 다음 동일한 치수의 다른 행렬을 만들고 -1s (최종 행렬)로 채우십시오. 그런 다음 초기 매트릭스를 반대하여 0에 맞을지 확인하십시오. 위치 (x, y)에 닿을 때 최종 행렬로 이동하여 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 행렬이 주어지면 해당 행에서 0을 검사하면 전체 행을 0으로 설정합니다. 내 솔루션의 시간 복잡성은 O (M * N)입니다. 테스트 용 정적 인구 배열이있는 전체 클래스와 콘솔에서 결과를 볼 수있는 디스플레이 배열 메소드를 공유하고 있습니다.
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();
}
