Проблема:
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image. Example: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,4,7,5,3,6,8,9] Explanation: Note: The total number of elements of the given matrix will not exceed 10,000.
Решение:
В моем подходе я пытаюсь пройти матрицу сверху вниз по диагонали и использую флаг «Обратный», чтобы переключать значения для получения зигзагообразного узора.
Позвольте мне объяснить, используя матрицу:
initial condition: i= 0; j=0, reverse = true;
so the pointers in matrix will be
j
|
v
i-> [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
we loop until j >=0 and i < row and i > -1
so the value fetched will be [1]
since the reverse flag is true, we will reverse the values of the array [1] =>[1]. then we toggle the value of reverse flag.
now push this values in to return matrix.
next time we increase the j value by 1 so the values will be
j =1, i =0, reverse = false.
so pointer will look like
j
|
v
i -> [ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]
we push the value to the new array [2] and increment the i value and decrement the j value
so pointer will look like
j
|
v, 2, 3 ]
i ->[ 4, 5, 6 ]
[ 7, 8, 9 ]
we push the value to the new array [4] and increment the i value and decrement the j value
on decrementing it becomes -1 so we skip the loop.
now the new array has the values [2,4]
since the reverse flag is false, we push the values to return matrix.
so return matrix will be [1,2,4]
now we increment the j = 2, i=0, reverse = true.
so pointer will look like
j
|
V
i -> [ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]
we push the value to the new array [3] and increment the i value and decrement the j value
so pointer will look like
j
|
V
[ 1, 2, 3 ]
i ->[ 4, 5, 6 ]
[ 7, 8, 9 ]
we push the value to the new array [5] and increment the i value and decrement the j value
so pointer will look like
j
|
V
[ 1, 2, 3 ]
[ 4, 5, 6 ]
i ->[ 7, 8, 9 ]
we push the value to the new array [7] and increment the i value and decrement the j value
on decrementing it becomes -1 so we skip the loop.
now the new array has the values [3,5,7]
since the reverse flag is true, we push the values to return matrix in reverse order.
so return matrix will be [1,2,4,7,5,3]
Now the column value is reached the max value. so, from now onwards the j starting value will be the max value, it will be decremented till max row value and the i will start from 1st and it will be incremented to the max row value.
so pointer will look like
j
|
V
[ 1, 2, 3 ]
i ->[ 4, 5, 6 ]
[ 7, 8, 9 ]
after j-- and i++,
so pointer will look like
j
|
V
[ 1, 2, 3 ]
[ 4, 5, 6 ]
i ->[ 7, 8, 9 ]
on incrementing the i, it`s more than the max row count. so the loop stops.
now the new array has the values [6,8]
since the reverse flag is false, we push the values to return matrix.
so return matrix will be [1,2,4,7,5,3,6,8]
now j= max value and i = i+1;
j
|
V
[ 1, 2, 3 ]
[ 4, 5, 6 ]
i ->[ 7, 8, 9 ]
and last value is added.
now the new array has the values [9]
since the reverse flag is true, we push the values to return matrix in reverse order.
so return matrix will be [1,2,4,7,5,3,6,8,9]
on incrementing the i, the basic condition i < rows of matrix fails and the loop ends.
Время выполнения приведенного выше алгоритма составляет o (m * n), а пространство для матрицы возврата будет o (m * n).
код в джаваскрипте:
var findDiagonalOrder = function(matrix) {
var returnMatrix = [],row = matrix.length, j= 0, reverse = true;
// check if the input matrix is 2d matrix. else return the returnmatrix;
if(matrix[0]){
var coloumn = matrix[0].length;
debugger;
// basically we are traversing from top to bottom in diagonally.
// we reverse the values of the traversing alternatively to create the zig-zag pattern
// we incress the coloumn values from 0 to max column values
// for each value of the j loop until the j = 0 and i value is less then row value
// we reverse the values according to reverse flag which toggles for every other time
while(j < coloumn){
var newarr = [];
var i = 0, k = j;
while( k >= 0 && i < row && i > -1){
if(matrix[i][k] != undefined){
newarr.push(matrix[i][k]);
}
i++;
k--;
}
if(reverse){
newarr.reverse();
}
reverse = !reverse;
newarr.forEach(elem => returnMatrix.push(elem));
j++;
}
// after reaching the max value of j
// the j never increases but the i value of the row
// increases and the j value decreases and i value increases
// similarly we add the values in the zigzag pattern using the reverse flag.
for(var l =1; l < row; l++){
var j = coloumn-1, i = 0+l;
var newarr =[];
//
while(j >= 0 && i < row ){
newarr.push(matrix[i][j]);
j--;
i++;
}
if(reverse){
newarr.reverse();
}
reverse = !reverse;
newarr.forEach(elem => returnMatrix.push(elem));
}
}
return returnMatrix;
};
Несколько важных входов и выходов:
testcases passed: i/p [] o/p: [] i/p [[]] o/p:[] i/p [[1,2,3,1,2,3],[4,5,6,2,3,4],[7,8,9,2,3,4],[7,8,9,2,3,4]] o/p: [1, 2, 4, 7, 5, 3, 1, 6, 8, 7, 8, 9, 2, 2, 3, 3, 2, 9, 2, 3, 4, 4, 3, 4]
