C++LeetCode(73.매트릭스 부 영)실현

[LeetCode]73.Set 매트릭스 제로
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
이 문 제 는 CareerCup 의 원제 라 고 합 니 다.저 는 아직 CareerCup 을 닦 지 않 아서 모 르 겠 습 니 다.그런데 이 문제 도 어렵 지 않 습 니 다.저도 인터넷 의 해법 을 보고 그대로 썼 지만 다음 에 만나면 꼭 생각 납 니 다.이 문제 에서 말 하 는 공간 복잡 도 는 O(mn)의 해법 이다.더 이상 말 할 필요 도 없 이 matrix 등 크기 의 행렬 을 새로 만 든 다음 에 한 줄 한 줄 쓸 고 0 만 있 으 면 새로 만 든 행렬 의 대응 행 전 부 를 0 으로 만 들 고 줄 을 다 쓸 고 다시 쓸 어 낸 다음 에 업 데 이 트 된 행렬 을 matrix 에 부여 하면 된다.이 알고리즘 은 공간 복잡 도가 너무 높다.이 를 O(m+n)로 최적화 하 는 방법 은 길이 가 m 인 1 차원 배열 로 각 줄 에 0 이 있 는 지,길이 가 n 인 1 차원 배열 로 각 열 에 0 이 있 는 지 를 기록 하고 마지막 으로 matrix 배열 을 직접 업데이트 하면 된다.이 문제 의 요 구 는 O(1)의 공간 을 사용 하 는 것 이다.그러면 우 리 는 배열 을 새로 만 들 수 없다.우 리 는 원래 배열 의 첫 번 째 줄 의 첫 번 째 열 로 각 줄 의 각 열 에 0 이 있 는 지 를 기록 하 는 것 을 고려 할 것 이다.
-첫 줄 의 첫 번 째 열 을 먼저 스 캔 하고 0 이 있 으 면 각자 의 flag 를 true 로 설정 합 니 다.
-그리고 첫 줄 의 첫 번 째 열 을 제외 한 전체 배열 을 스 캔 하고 0 이 있 으 면 해당 하 는 첫 줄 과 첫 번 째 열 에 있 는 숫자 를 0 으로 부여 합 니 다.
-첫 번 째 줄 의 첫 번 째 열 을 제외 한 전체 배열 을 다시 옮 겨 다 니 며,첫 번 째 줄 과 첫 번 째 열 에 해당 하 는 숫자 가 0 이면 현재 값 을 0 으로 부여 합 니 다.
-마지막 으로 첫 번 째 줄 의 첫 번 째 줄 의 flag 에 따라 첫 번 째 줄 의 첫 번 째 열 을 업데이트 합 니 다.
코드 는 다음 과 같 습 니 다:

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 rowZero = false, colZero = false;
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) colZero = true;
        }
        for (int i = 0; i < n; ++i) {
            if (matrix[0][i] == 0) rowZero = true;
        } 
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowZero) {
            for (int i = 0; i < n; ++i) matrix[0][i] = 0;
        }
        if (colZero) {
            for (int i = 0; i < m; ++i) matrix[i][0] = 0;
        }
    }
};

C++구현 LeetCode(73.매트릭스 부 영)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 매트릭스 부 영 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!