매트릭스 제로 설정-매트릭스 제로 설정 LeetCode 매트릭스 제로 설정

Twitter Facebook 링크드 인 버퍼 레딧 텀블러

집합 행렬 XNUMX 문제에서 (n X m) 매트릭스, 요소가 0이면 전체 행과 열을 0으로 설정합니다.

차례

예

입력:
{
[1, 1, 1]
[1, 0, 1]
[1, 1, 1]
}
출력:
{
[1, 0, 1]
[0, 0, 0]
[1, 0, 1]
}

입력:
{
[0,1,2,0]
[3,4,5,2]
[1,3,1,5]
}
출력:
{
[0,0,0,0]
[0,4,5,0]
[0,3,1,0]
}

행렬 XNUMX 설정에 대한 순진한 접근 방식

크기 (n X m)의 배열 답을 만들고 모든 요소를 1로 초기화합니다.
행렬 배열을 행 방향으로 순회하고 현재 행에 0과 같은 요소가 포함되어 있으면 응답 배열에서 현재 행을 0으로 설정합니다.
행렬 배열을 열 방향으로 순회하고 현재 열에 0과 같은 요소가 포함 된 경우 현재 열을 답변 배열에서 0으로 설정합니다.
이제 답 배열을 탐색합니다. 현재 요소가 0이면 행렬 배열에서이 요소를 0으로 설정합니다.
반환 행렬 정렬.

의사 코드

Initialize all the elements of array answer as 1
for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    if (matrix[i][j] == 0) {
      set row i as 0(zero) in answer array
      break
    }
  }
}
for (int j = 0; j < m; j++) {
  for (int i = 0; i < n; i++) {
    if (matrix[i][j] == 0) {
      set column j as 0(zero) in matrix array
    }
    break
  }
}
for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    if (answer[i][j] != 0) {
      answer[i][j] = matrix[i][j]
    }
  }
}
return answer array

매트릭스 제로 설정을위한 JAVA 코드

public class SetMatrixZeroes {
    private static void setZeroes(int[][] matrix, int n, int m) {
        int answer[][] = new int[n][m];

        // Set all elements of answer array as 1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                answer[i][j] = 1;
            }
        }

        // Traverse row wise
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    // Set this row as zero in answer array
                    for (int k = 0; k < m; k++) {
                        answer[i][k] = 0;
                    }
                    break;
                }
            }
        }

        // Traverse column wise
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                if (matrix[i][j] == 0) {
                    // Set this column as 0 in answer array
                    for (int k = 0; k < n; k++) {
                        answer[k][j] = 0;
                    }
                }
            }
        }

        // Update the elements in matrix array
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (answer[i][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[][] matrix = new int[][] {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int n = matrix.length;
        int m = matrix[0].length;

        setZeroes(matrix, n, m);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

        // Example 2
        matrix = new int[][] {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        n = matrix.length;
        m = matrix[0].length;
        
        setZeroes(matrix, n, m);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

행렬 XNUMX 설정을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

void setZeroes(vector<vector<int>> &matrix, int n, int m) {
    vector<vector<int>> answer;
    
    // Set all elements of answer array as 1
    for (int i = 0; i < n; i++) {
        vector<int> curr;
        for (int j = 0; j < m; j++) {
            curr.push_back(1);
        }
        answer.push_back(curr);
    }
        
    // Traverse row wise
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                for (int k = 0; k < m; k++) {
                    answer[i][k] = 0;
                }
                break;
            }
        }
    }
        
    // Traverse column wise
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            if (matrix[i][j] == 0) {
                for (int k = 0; k < n; k++) {
                    answer[k][j] = 0;
                }
            }
        }
    }
        
    // Update the elements in matrix array
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (answer[i][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
}

int main() {
    // Example 1
    vector<vector<int>> matrix{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
    int n = matrix.size();
    int m = matrix[0].size();

    setZeroes(matrix, n, m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }

    // Example 2
    vector<vector<int>> matrix2{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
    n = matrix2.size();
    m = matrix2[0].size();

    setZeroes(matrix2, n, m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<matrix2[i][j]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

복잡성 분석

시간 복잡성 = O (n * m)
공간 복잡성 = O (n * m)
여기서 n은 행렬의 행 수이고 m은 행렬의 열 수입니다.

행렬 제로 설정을위한 최적의 접근 방식

시간 복잡도를 더 줄일 수는 없지만 공간 복잡도를 O (1)로 최적화 할 수 있습니다.

-9999가 행렬 배열에서 발생하지 않는다고 가정하면

현재 행에 0과 같은 요소가 포함되어있는 경우 행렬 배열을 행 방향으로 탐색하고 9999이 아닌 현재 행의 모든 요소를 -0로 설정합니다.
현재 열에 0과 같은 요소가 포함 된 경우 행렬 배열을 열 단위로 탐색하고 9999이 아닌 현재 열의 모든 요소를 -0로 설정합니다.
다시 행렬을 탐색하고 -9999 인 모든 요소를 0으로 설정합니다.
행렬 배열을 반환합니다.

예

핀

JAVA 코드

public class SetMatrixZeroes {
    private static void setZeroes(int[][] matrix, int n, int m) {
        // Traverse row wise
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    // Set all the elements that are not zero as -9999
                    for (int k = 0; k < m; k++) {
                        if (matrix[i][k] != 0) {
                            matrix[i][k] = -9999;
                        }
                    }
                }
            }
        }

        // Traverse column wise
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                if (matrix[i][j] == 0) {
                    // Set all the elements that are not zero as -9999
                    for (int k = 0; k < n; k++) {
                        if (matrix[k][j] != 0) {
                            matrix[k][j] = -9999;
                        }
                    }
                }
            }
        }
        
        // Update all -9999 as 0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == -9999) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[][] matrix = new int[][] {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int n = matrix.length;
        int m = matrix[0].length;

        setZeroes(matrix, n, m);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

        // Example 2
        matrix = new int[][] {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        n = matrix.length;
        m = matrix[0].length;

        setZeroes(matrix, n, m);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

void setZeroes(vector<vector<int>> &matrix, int n, int m) {
    // Traverse row wise
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                // Set all the elements that are not zero as -9999
                for (int k = 0; k < m; k++) {
                    if (matrix[i][k] != 0) {
                        matrix[i][k] = -9999;
                    }                        
                }
                break;
            }
        }
    }
        
    // Traverse column wise
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            if (matrix[i][j] == 0) {
                // Set all the elements that are not zero as -9999
                for (int k = 0; k < n; k++) {
                    if (matrix[k][j] != 0) {
                        matrix[k][j] = -9999;
                    }
                }
            }
        }
    }
        
    // Update all -9999 as 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == -9999) {
                matrix[i][j] = 0;
            }
        }
    }
}

int main() {
    // Example 1
    vector<vector<int>> matrix{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
    int n = matrix.size();
    int m = matrix[0].size();

    setZeroes(matrix, n, m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }

    // Example 2
    vector<vector<int>> matrix2{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
    n = matrix2.size();
    m = matrix2[0].size();

    setZeroes(matrix2, n, m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<matrix2[i][j]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

복잡성 분석

시간 복잡성 = O (n * m)
공간 복잡성 = O (1)
여기서 n은 행렬의 행 수이고 m은 행렬의 열 수입니다.

참조

Twitter Facebook 링크드 인 버퍼 레딧 텀블러