LeetCode 알고리즘 문제 73: 매트릭스 제로 분석
19184 단어 Leetcode 알고리즘 문제 분석
예시 1:
:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
예시 2:
:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
진급:
이 문제 의 전체적인 사상 은 공간 을 줄 이 는 것 이다. 개선 방안 은 두 개의 1 차원 배열 로 행렬 정 보 를 기록 할 수 있다. 만약 에 특정한 줄 이나 특정한 열 에 0 이 있 으 면 배열 의 대응 위 치 를 0 으로 한 다음 에 마지막 으로 이 두 개의 1 차원 배열 에 따라 행렬 을 조작 하 는 것 이다.상수 공간 을 사용 하려 면 두 개의 표지 로 첫 줄 과 첫 번 째 열 을 기록 한 다음 에 첫 줄 과 첫 번 째 열 로 대응 하 는 행렬 의 0 정 보 를 기록 할 수 있다. 0 만 있 으 면 행렬 이 모두 0 이기 때문에 0 이 있 으 면 첫 줄 과 첫 번 째 열의 대응 위 치 를 0 으로 설정 하면 된다.마지막 으로 첫 번 째 줄 과 첫 번 째 열 에 따라 전체 행렬 을 첫 번 째 줄 과 첫 번 째 열 을 제외 한 부분 을 처리 한 다음 에 두 개의 표지 에 따라 첫 번 째 줄 과 첫 번 째 열 을 처리한다.
C + + 소스 코드:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if(matrix.empty() || matrix[0].empty()) return;
int m = matrix.size(), n = matrix[0].size();
bool row_flag=false, col_flag=false;
for(int i=0;i<m;i++){
if(matrix[i][0] == 0)
row_flag = true;
}
for(int j=0;j<n;j++){
if(matrix[0][j] == 0)
col_flag = true;
}
for(int i=1;i<m;i++)
for(int j=1;j<n;j++){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
for(int i=1;i<m;i++)
for(int j=1;j<n;j++){
if(matrix[i][0]==0 || matrix[0][j]==0)
matrix[i][j] = 0;
}
if(row_flag)
for(int i=0;i<m;i++)
matrix[i][0] = 0;
if(col_flag)
for(int j=0;j<n;j++)
matrix[0][j] = 0;
}
};
python 3 소스 코드:
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
if len(matrix)==0 or len(matrix[0])==0:
return
m = len(matrix)
n = len(matrix[0])
rowFlag = False
colFlag = False
for i in range(m):
if matrix[i][0]==0:
rowFlag = True
for j in range(n):
if matrix[0][j]==0:
colFlag = True
for i in range(1, m):
for j in range(1, n):
if matrix[i][j]==0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0]==0 or matrix[0][j]==0:
matrix[i][j] = 0
if rowFlag:
for i in range(m):
matrix[i][0] = 0
if colFlag:
for j in range(n):
matrix[0][j] = 0
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 알고리즘 문제 73: 매트릭스 제로 분석직접적인 해결 방안 은 O (mn) 의 추가 공간 을 사용 하 는 것 이지 만 이것 은 좋 은 해결 방안 이 아니다. 간단 한 개선 방안 은 O (m + n) 의 추가 공간 을 사용 하 는 것 이지 만 이것 은 가장...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.