매트릭스 제로 설정

난이도 중급
자주 묻는 질문 아마존 Apple Facebook Microsoft 신탁 Paytm
배열 매트릭스조회수 126

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

집합 행렬 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 설정에 대한 순진한 접근 방식

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

의사 코드

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;
}
1 0 1 
0 0 0 
1 0 1 
0 0 0 0 
0 4 5 0 
0 3 1 0 

복잡성 분석

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

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

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

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

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

매트릭스 제로 설정

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;
}
1 0 1 
0 0 0 
1 0 1 
0 0 0 0 
0 4 5 0 
0 3 1 0 

복잡성 분석

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

참조

균열 시스템 설계 인터뷰
Translate »