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.
Mündəricat
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
- (N X m) ölçülü bir sıra cavabı yaradın və hər elementi 1 olaraq başlatın.
- 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.
- 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.
- İndi cavab massivini keçin, cari element 0 olarsa, bu elementi bir matris massivində 0 olaraq təyin edin.
- 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
- 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.
- 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.
- Yenidən matrisdən keçin və -9999 olan bütün elementləri 0-a qoyun.
- Matris dizisini qaytarın.
misal
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ı.
