해당 행이나 열에 0이 포함되어 있으면 행렬의 모든 셀을 0으로 설정하십시오.
0과 1의 NxN 행렬이 주어집니다. 을 포함하는 모든 행 세트 0모두 0들와를 포함하는 모든 열 설정 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 엔지니어는 추가 메모리가 필요없고 부울 변수 두 개와 패스 한 개만 포함 된 솔루션이 있다고 답했습니다. 그래서 그 답을 찾고 있습니다.
BTW, 비트 행렬이라고 가정하면 1과 0만이 행렬에있을 수 있습니다.
자, 여기 3AM이기 때문에 피곤하지만 행렬의 각 숫자에 정확히 2 패스를 사용하여 첫 번째 시도를 시도하므로 O (NxN)에서 행렬의 크기는 선형입니다.
첫 번째 열과 첫 번째 행을 마커로 사용하여 행이 1 / 1 인 행을 알 수 있습니다. 그런 다음 첫 번째 행 / 열도 모두 1인지 기억해야 할 두 개의 변수 l과 c가 있습니다. 따라서 첫 번째 패스는 마커를 설정하고 나머지는 0으로 재설정합니다.
두 번째 패스는 행과 열이 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으로 변경해야합니다.
최신 정보
사람들은 N을 고정 값 (예 : 8)으로 제한하면이 문제를 해결할 수 있다고 생각하는 것 같습니다. 그것은 a) 요점을 놓치고 b) 원래의 질문이 아닙니다. 정렬에 대한 질문을 게시하지 않고 "8 가지만 정렬하고 싶다"고 가정 한 답변을 기대합니다.
즉, N이 실제로 8로 제한되어 있음을 알고 있다면 합리적인 접근 방법입니다. 위의 대답은 그러한 회귀가없는 원래의 질문에 대답합니다.
그래서 내 생각은 마지막 행 / 열의 값을 플래그로 사용하여 해당 열 / 행의 모든 값이 1인지 여부를 나타냅니다.
마지막 행 / 열을 제외한 전체 매트릭스를 통해 지그재그 스캔 을 사용합니다 . 각 요소에서 최종 행 / 열의 값을 현재 요소의 값과 함께 논리 AND로 설정합니다. 다시 말해, 0을 누르면 최종 행 / 열이 0으로 설정됩니다. 1이면 최종 행 / 열의 값은 이미 1 인 경우에만 1이됩니다. 어쨌든 현재 요소를 0으로 설정하십시오.
완료되면 해당 열 / 행이 1로 채워진 경우 최종 행 / 열에 1이 있어야합니다.
마지막 행과 열을 통해 선형 스캔을 수행하고 1을 찾으십시오. 마지막 행과 열이 모두 1 인 행렬 본문의 해당 요소에 1을 설정합니다.
코딩은 개별 오류를 피하는 것이 까다로울 수 있지만 한 번에 작동해야합니다.
여기에 해결책이 있으며 단일 패스로 실행되며 추가 메모리없이 "제자리에서"모든 처리를 수행합니다 (스택을 늘리기 위해 저장).
재귀를 사용하여 0의 쓰기를 지연시키고 다른 행과 열의 행렬을 파괴합니다.
#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으로 변경하십시오. 두 단계로 수행하는 것이 좋습니다. 첫 번째 단계에서는 어떤 행과 열을 제로화해야하는지에 대한 정보를 수집합니다 (정보는 배열에 저장되므로 추가 메모리를 사용하고 있음). 두 번째 패스는 값을 변경합니다. 나는 그것이 당신이 찾고있는 해결책이 아니라는 것을 알고 있지만 그것이 실용적인 것이라고 생각합니다. 주어진 제한 조건으로 인해 문제점을 해결할 수 없습니다.
두 개의 정수 변수와 두 개의 패스 (최대 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)
두 단계를 거치는 또 다른 솔루션은 가로 및 세로로 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
}
}
단일 패스에서 그렇게해야하지만 CPU가 단일 행에서 산술을 수행하기에 N이 작다는 가정이 있습니다. 그렇지 않으면 각 행을 반복하여 모든 행인지 확인해야합니다 1s 또는 믿습니다. 그러나 알고리즘에 대해 질문하고 하드웨어를 제한하지 않으면 "N 비트 산술을 지원하는 CPU 빌드 ..."로 대답을 시작합니다.
다음은 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);
뭔가 빠졌습니까?
좋은 challange. 이 솔루션은 스택에 생성 된 두 개의 부울 만 사용하지만 함수가 재귀 적이므로 스택에 부울이 여러 번 생성됩니다.
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;
}
사실은. 알고리즘을 실행하고 결과를 인쇄하려면 (즉, 복원하지 않으면) 한 번에 쉽게 수행 할 수 있습니다. 알고리즘을 실행할 때 배열을 수정하려고하면 문제가 발생합니다.
여기 내 해결책이 있습니다. 단지 (i, j) 요소의 행 / 열 값을 AND로 AND 인쇄하는 것과 관련이 있습니다.
#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 # 에서이 문제를 해결하려고했습니다.
실제 행렬과 차원을 나타내는 n을 제외하고 두 개의 루프 변수 (i와 j)를 사용했습니다.
내가 시도한 논리는 다음과 같습니다.
- 행렬의 각 동심원에 관련된 행과 열에 대한 AND 계산
- 모서리 셀에 저장하십시오 (시계 반대 방향으로 저장했습니다)
- 두 개의 부울 변수는 특정 제곱을 평가할 때 두 모퉁이의 값을 유지하는 데 사용됩니다.
- 이 과정은 외부 루프 (i)가 중간에있을 때 종료됩니다.
- 코너 셀 (나머지 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 bools와 2 int로 줄이지 않았지만 가능하다면 놀라지 않을 것입니다. 각 셀의 약 3 읽기 및 3 쓰기를 수행하며 O (N ^ 2) 여야합니다. 배열 크기에서 선형.
이 문제를 해결하기 위해 몇 시간을 걸렸습니다. 인터뷰의 압력으로 그것을 끝내고 싶지는 않습니다! 내가 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와 높이를 확인하여 수행됩니다 각 반복에서 -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행렬의 크기입니다.
그런 다음 입력을 반복하십시오. 더 공간 효율적으로 확장 할 수 있습니까?
하나의 매트릭스 스캔, 두 개의 부울, 재귀 없음
두 번째 패스를 피하는 방법? 두 번째 패스는 0이 끝에 나타날 때 행이나 열을 지우는 데 필요합니다.
그러나 행 #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)) 색인이있는 요소를 고려하기 전에> i.
이것이 효과가 있기를 바랍니다 (havent testet)
이것은 C ++의 다른 N에 대해 테스트 되었으며
ONE PASS , TWO BOOLS , NO RECURSION , NO EXTRA MEMORY , Arbortralyly Large N N에 대한 홀드
입니다.
더 구체적으로, 나는 두 개의 루프 카운터를 사용하는 것이 좋습니다. 나는 두 개의 const unsigned를 가지고 있는데, 가독성을 위해 매번 계산되는 것이 아니라 존재합니다. 외부 루프 간격은 [0, N]이고 내부 루프 간격은 [1, n-1]입니다. switch 문은 대부분 루프에 있으며 실제로는 하나의 패스라는 것을 매우 명확하게 보여줍니다.
알고리즘 전략 :
첫 번째 요령은 행렬의 내용을 누적하기 위해 행렬 자체에서 행과 열을 만드는 것입니다.이 메모리는 첫 번째 행과 열에서 알아야 할 모든 것을 두 개의 부울로 오프로드하여 사용할 수 있습니다. 두 번째 요령은 하위 행렬과 그 지수의 대칭을 사용하여 하나에서 두 패스를 얻는 것입니다.
알고리즘 개요 :
- 첫 번째 행을 스캔하고 모두 부울에있는 경우 저장하고 결과를 두 번째 부울에 저장하는 첫 번째 열에 대해 동일하게 수행하십시오.
- 첫 번째 행과 첫 번째 열을 제외한 하위 행렬의 경우 : 단락을 읽을 때와 같이 왼쪽에서 오른쪽으로, 위에서 아래로 반복합니다. 각 요소를 방문하면 하위 행렬을 반대로 방문하면 방문 할 해당 요소도 방문합니다. 방문한 각 요소와 해당 값이 해당 행이 첫 번째 열과 교차하는 위치 및 해당 열과 첫 번째 행이 교차하는 위치의 값
- 하위 행렬의 중심에 도달하면 위와 같이 두 요소를 동시에 계속 방문하십시오. 그러나 이제 방문한 요소의 값을 행이 첫 번째 열과 교차하는 위치와 열이 첫 번째 행과 교차하는 AND로 설정하십시오. 그런 다음 하위 행렬이 완료됩니다.
- 구걸 할 때 계산 된 두 개의 부울 변수를 사용하여 첫 번째 행과 첫 번째 열을 올바른 값으로 설정하십시오.
템플릿 화 된 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;
}
좋아, 나는 그것이 일치하는 것이 아니라는 것을 알고 있지만 두 개의 bools 대신 bool과 1 바이트를 사용하여 한 번에 얻었습니다 ... 또한 그것의 효율성을 보증하지는 않지만 이러한 유형의 질문은 종종 최적의 솔루션보다 덜 필요합니다.
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);
}
}
테스트가 포함 된 Ruby 구현은 다음과 같습니다 .O (MN) 공간이 필요합니다. 실시간 업데이트를 원한다면 (0을 찾는 첫 번째 루프를 기다리지 않고 0을 찾을 때 결과를 표시하는 것과 같이) 다른 클래스 변수를 만들 수 있습니다 .0 @output을 찾을 때마다 업데이트 @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에 도달하는지 확인합니다. location (x, y)에 도달하면 최종 행렬로 이동하여 행 x를 0으로 채우고 열 y를 0으로 채 웁니다. 최종 행렬을 읽은 후 값이 -1 (원래 값)이면 초기 행렬의 동일한 위치에있는 값을 final로 복사하십시오.
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;
}
here is my solution. As you can see from the code, given a M * N matrix, it sets the entire row to zero once it inspects a zero in that row.the time complexity of my solution is O(M * N) . I am sharing the whole class which has a static populated array for testing and a display array method to see the result in the console.
public class EntireRowSetToZero {
static int arr[][] = new int[3][4];
static {
arr[0][0] = 1;
arr[0][1] = 9;
arr[0][2] = 2;
arr[0][3] = 2;
arr[1][0] = 1;
arr[1][1] = 5;
arr[1][2] = 88;
arr[1][3] = 7;
arr[2][0] = 0;
arr[2][1] = 8;
arr[2][2] = 4;
arr[2][3] = 4;
}
public static void main(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 - I have traversed the input only once but used a new array and only two extra Boolean variables.
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();
}
'Programing' 카테고리의 다른 글
| 언제 Flask.g을 사용해야합니까? (0) | 2020.06.10 |
|---|---|
| 공개 친구 교환 회원 기능 (0) | 2020.06.10 |
| C에서 괄호는 스택 프레임 역할을합니까? (0) | 2020.06.09 |
| mavn에서 mvn가 정확히 무엇을 설치합니까? (0) | 2020.06.09 |
| invokedynamic이란 무엇이며 어떻게 사용합니까? (0) | 2020.06.09 |