Matrix Zeroes seçin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Facebook microsoft Kahin Paytm
Geyim MatrisBaxılıb 126

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Set matris sıfır problemində, (n X m) verdik matris, bir element 0 olarsa, bütün sətirini və sütunu 0 seçin.

Nümunələr

Input:
{
[1, 1, 1]
[1, 0, 1]
[1, 1, 1]
}
Çıxış:
{
[1, 0, 1]
[0, 0, 0]
[1, 0, 1]
}

Input:
{
[0,1,2,0]
[3,4,5,2]
[1,3,1,5]
}
Çıxış:
{
[0,0,0,0]
[0,4,5,0]
[0,3,1,0]
}

Set Matrix Zeroes üçün sadəlövh yanaşma

  1. (N X m) ölçülü bir sıra cavabı yaradın və hər elementi 1 olaraq başlatın.
  2. Matris dizisini cərgəyə görə keçin və cari sıra 0-a bərabər bir element ehtiva edirsə, cavab cərgəsində cari cərgəni 0 olaraq təyin edin.
  3. Matrix array sütununa görə keçin və cari sütunda 0-a bərabər bir element varsa, cavab massivində cari sütunu 0 olaraq təyin edin.
  4. İndi cavab massivini keçin, cari element 0 olarsa, bu elementi bir matris massivində 0 olaraq təyin edin.
  5. Matrix qayıt array.

Saxta Kod

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

Set Matrix Zeroes üçün JAVA Kodu

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();
        }
    }
}

Set Matrix Zeroes üçün C ++ Kodu

#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 

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n * m)
Kosmik Mürəkkəblik = O (n * m) 
burada n - matrisdəki satır sayı və m - matrisdəki sütun sayı.

Set Matrix Zeroes üçün optimal yanaşma

Zaman mürəkkəbliyi daha da azaldıla bilməz, ancaq kosmik mürəkkəbliyi O (1) səviyyəsinə endirə bilərik.

-9999 olduğunu düşünsək, matris massivində baş vermir, onda

  1. Matris dizisini cərgəyə görə keçin və cari cərgədə 0-a bərabər bir element varsa, cari cərgənin 9999 olmayan bütün elementlərini -0 olaraq təyin edin.
  2. Matrix array sütunu ilə keçin və cari sütunun 0-a bərabər bir elementi varsa, cari sütunun 9999 olmayan bütün elementlərini -0 olaraq təyin edin.
  3. Yenidən matrisdən keçin və -9999 olan bütün elementləri 0-a qoyun.
  4. Matris dizisini qaytarın.

misal

Matrix Zeroes seçinPin

JAVA Kodu

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 ++ kodu

#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 

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n * m)
Kosmik Mürəkkəblik = O (1) 
burada n - matrisdəki satır sayı və m - matrisdəki sütun sayı.

References

Crack Sistemi Dizayn Müsahibələri
Translate »