DiagonalTraverse [source code]
public class DiagonalTraverse {
static
/******************************************************************************/
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0)
return new int[0];
int M = matrix.length, N = matrix[0].length;
int[] res = new int[M * N];
int p = 0;
res[p++] = matrix[0][0];
for (int k = 1; k <= M - 1 + N - 1; k++) {
if (k % 2 == 1) {
int xStart = getEdgeX(k, M, N, true), xEnd = getEdgeX(k, M, N, false);
for (int i = xStart; i <= xEnd; i++)
res[p++] = matrix[i][k - i];
} else {
int xStart = getEdgeX(k, M, N, false), xEnd = getEdgeX(k, M, N, true);
for (int i = xStart; i >= xEnd; i--)
res[p++] = matrix[i][k - i];
}
}
return res;
}
public int getEdgeX(int k, int M, int N, boolean isUpper) {
if (isUpper) {
if (k - 0 <= N - 1)
return 0;
else
return k - (N - 1);
} else {
if (k - 0 <= M - 1)
return k;
else
return M - 1;
}
}
}
/******************************************************************************/
public static void main(String[] args) {
DiagonalTraverse.Solution tester = new DiagonalTraverse.Solution();
int[][][] inputs = {
{
{1,2,3},
{4,5,6},
{7,8,9},
},
{{6,9,7}},
};
int[][] answers = {
{1,2,4,7,5,3,6,8,9},
{6,9,7},
};
for (int i = 0; i < inputs.length; i++) {
int[][] matrix = inputs[i];
int[] ans = answers[i];
System.out.println(Printer.separator());
String outputStr = Printer.array(tester.findDiagonalOrder(matrix));
String ansStr = Printer.array(ans);
System.out.println(
Printer.wrapColor(Matrix.printMatrix(matrix), "magenta") +
" -> " + outputStr +
Printer.wrapColor(", expected: \n" + ansStr, ansStr.equals(outputStr) ? "green" : "red")
);
}
}
}
这个问题刚拿到的时候确实是一点思路都没有的; 好像上425的时候听Jason他们提过一次, 但是他们并没有讲具体的算法; 所以现在一筹莫展, 只能用笨办法人逻辑的方法先搞起来; 这个问题要做的是一个traversal, 所以最后你要关注的其实就是index的变化趋势; 想不出来什么趋势, 搞一个例子, 然后自己trace一下看看有没有什么规律: from result to computation;
题目给出来的例子是一个square, 也就是长宽相等的, 我认为这个好像不利于generalize这里的规律, 所以我自己写的时候用的是一个3x4的rectangle;
知道了一个trace之后, 不代表就知道computation了; 什么是computation, 比如这一题, 你trace画下来, 对于一个3x4的rectangle: (0,0)|(0,1),(1,0)|(2,0),(1,1),(0,2)|(0,3),(1,2),(2,1)|...;
这样一个trace/sequence是不是就等价于告诉你这里要做的computation了呢? 当然不是; 这一题, 首先很明显你要写的是一个循环算法; 其次, 你有了这个trace, 想要转化成为computation: 你就要思考你每一个iteration要做的事情: what is each iteration? 那么你就要看你这个trace了啊, 有那么多种. 你要怎样设计你的逻辑, 比如保证能让(0,1)到达(1,0), 能让(0,2)到达(0,3)等等;
当然, 说了这么多, 还是有点看不出来这个题目的intuition是什么; 好像有点想法了: 这个问题traverse的时候有两个难点:
- 矩形边界造成的cutoff怎么出力? 首先, 你的traversal/iteration要有一个自然的过程, 这个自然的过程就是x + y = k这个直线簇不断移动形成的三角形. 至于矩形边界, 用filter类型的conditional来处理就行了;
- 不同的k对应的直线, 我们的方向不一样? 这个也简单, 因为其实是两个方向交替的, 这种一个binary flag处理一下就行了;
- 更简单的, 因为每一个直线对应一个k, 我们是每隔一个k相同方向, 相邻的k相反方向, 所以直接用k的奇偶性就可以处理了;
大概想好了之后, 还算是按时AC了; 最后的速度是349ms (3%), 出乎意料的慢. 仔细想了一想我这个算法到底哪里有问题? 好像就一个问题, 我有两个循环; 而且我是走满了的: 我是走的整个三角形. 如果比如我们实际上拿到的是一个M*1的矩阵, 我结果还是走了一个三角形. 这里加速的关键应该是premature exit; 当出现出界(在三角形内但是不在矩形内)的情况的时候, 不应该是单纯的skip, 而应该是直接就可以break了;
下面是这个很慢的版本的代码:
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0)
return new int[0];
int M = matrix.length, N = matrix[0].length;
int[] res = new int[M * N];
int p = 0;
res[p++] = matrix[0][0];
for (int k = 1; k <= M - 1 + N - 1; k++) {
for (int i = 0; i <= k; i++) {
int j = k - i;
if (k % 2 == 1) {
if (i < M && j < N)
res[p++] = matrix[i][j];
} else {
if (j < M && i < N)
res[p++] = matrix[j][i];
}
}
}
return res;
}
}
事实上, 我们真的有必要走三角形吗? 知道这个平行线簇之后, 我们其实是可以直接算出来这些线跟矩形边界的交点的;
这么一说这个东西好像还是比我425课上他们讨论的单纯的traversal要复杂一些的; 这个矩形边界的处理好像是这个算法加速的关键; 我上面那种filter的处理方式显然还不够优秀;
这个交点的计算方式好像不是特别容易, 但是应该是能算出来的; 最后优化出来就是上面这个算法, 速度是8(60), 总算是正常了; 注意这个代码是可以继续优化一下, 写的更简练的, 毕竟有一些的重复代码. 不对, 思考了一下, 优化空间好像不大(优化无非就是把k是奇偶数两种情况的代码整合到一起, 但是两个循环header的重点, 一个是geq, 一个是leq, 这个好像没有办法整合到一个循环里面去);
不过还是那句话, 不要执迷于Premature Optmization; AC比写的好看更重要;
customize increments
这个思路其实我之前在做survival project的时候, 自己都想到过, 但是这里却没有想到; 事实上, 这个问题还很典型的是一个需要这个思路的题目: iteration的方向变化的问题;
discussion最优解就是这样的;
@shawngao said in Concise Java Solution:
I don't think this is a hard problem. It is easy to figure out the walk pattern. Anyway...
Walk patterns:
- If out of
bottom border(row >= m) then row = m - 1; col += 2; change walk direction.- if out of
right border(col >= n) then col = n - 1; row += 2; change walk direction.- if out of
top border(row < 0) then row = 0; change walk direction.- if out of
left border(col < 0) then col = 0; change walk direction.- Otherwise, just go along with the current direction.
Time complexity: O(m * n), m = number of rows, n = number of columns.
Space complexity: O(1).
public class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) return new int[0];
int m = matrix.length, n = matrix[0].length;
int[] result = new int[m * n];
int row = 0, col = 0, d = 0;
int[][] dirs = {{-1, 1}, {1, -1}};
for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row += dirs[d][0];
col += dirs[d][1];
if (row >= m) { row = m - 1; col += 2; d = 1 - d;}
if (col >= n) { col = n - 1; row += 2; d = 1 - d;}
if (row < 0) { row = 0; d = 1 - d;}
if (col < 0) { col = 0; d = 1 - d;}
}
return result;
}
}
我只能说这些人对于iteration的理解还是比我要深刻; 我脑子里的iteration的规律, 还是局限于直线型的, 所以我这个问题只知道用平行线簇的方式来做, 还有一堆用来调整配合这种iteration思路的小技巧, 最后就花了很多的时间;
但是你看别人, 很自然的就知道怎么直接在一个矩形里面iterate; 当然, 确实是用了定制increment这样的技巧; 但是nonetheless, 还是体现出来人家对于iteration本质的理解比我深刻;
另外注意这里的一个处理细节上的区别: 首先, 我们一次只能写一个循环, 但是这个题目里面, 这个循环要同时处理两个东西, 一个是二维的矩阵, 一个是一维的array, 一个是输入, 一个是输出.
- 二维和一维之间的index的转化问题我们已经知道怎么做了, 很熟悉了:
- 一维到二维, 用mod(length of row)操作就行了;
- 二维到一维, 直接二维的走着, 然后一维用一个end pointer不停更新就行了;
- 一个循环处理两个结构的iteration, 一般常见的思路就是我们循环里面的loop var就是两个结构的其中一个的index, 然后另外一个结构的index呢, 就直接用一个类似变量的方式更新就行了; 我的做法当中, 我对二维的index进行loop, 他这个做法当中, 是对一维的index进行循环; 注意他这里对于matrix的二维index, 还是用的两个, 而不是一个再去mod: 那样很麻烦, 没有必要;
其实类似他这里的, 对两个坐标进行撞墙或者反弹式的更新的思路我也想到过, 但是我就是感觉这个traverse的方向无法处理; 主要还是没有想到这个定制increment的思路;
另外他这个代码还可以进一步简化:
@StefanPochmann said in Concise Java Solution:
No need for the
dirsarray, you can just alternatedbetween1and-1and add/subtract it.
public class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) return new int[0];
int m = matrix.length, n = matrix[0].length;
int[] result = new int[m * n];
int row = 0, col = 0, d = 1;
for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row -= d;
col += d;
if (row >= m) { row = m - 1; col += 2; d = -d;}
if (col >= n) { col = n - 1; row += 2; d = -d;}
if (row < 0) { row = 0; d = -d;}
if (col < 0) { col = 0; d = -d;}
}
return result;
}
}
确实是这样的, 他这个dir array里面的数据这么有规律性, 明显直接简化成一个变量就可以了; 不过这种东西还是事后优化比较好, AC之前写的代码冗余一点也无所谓;
他这个代码我跑了一下, 居然没有我的ver2快: 9(37). 有点奇怪;
在Stefan这个简化的基础上, 还有人提出了这个解法:
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0) return new int[0];
int r = 0, c = 0, m = matrix.length, n = matrix[0].length, arr[] = new int[m * n];
for (int i = 0; i < arr.length; i++) {
arr[i] = matrix[r][c];
if ((r + c) % 2 == 0) { // moving up
if (c == n - 1) { r++; }
else if (r == 0) { c++; }
else { r--; c++; }
} else { // moving down
if (r == m - 1) { c++; }
else if (c == 0) { r++; }
else { r++; c--; }
}
}
return arr;
}
这个解法我思考了一下, 可以说是这个问题的最优秀的解法了; 注意他declaration这一行, 最后arr这个array居然也能挤进去同一行, 是怎么做到的;
首先, 这个人的做法跟上面两个做法都不一样, 他这个做法是考虑了diagonal这个概念的; 这个跟我的算法有相似之处;
但是, 他这个算法跟我的算法一个不一样的地方在于, 他对于这个diagonal的概念的利用更加巧妙和彻底; 他首先认识到, 两种(奇偶性)的diagonal的取值就对应于两个不同的state; state是什么呢, 可以当做是一个flag; 这个flag有什么内涵呢? 当x和y当中有任何一个取到边界值的时候, 在不同的state下, 我们下一步的处理应该是不同的;
conditional increment
之前有介绍过conditional increment这个技巧, 不过当时的作用纯粹是为了让代码更简洁一些; 但是这里这个conditional increment的使用, 相对就巧妙很多;
你可以看, 比如这个branch:
if ((r + c) % 2 == 0) { // moving up
if (c == n - 1) { r++; } //1
else if (r == 0) { c++; } //2
else { r--; c++; } //3
}
对应的是偶数的state; 你看, 他下面的三个branch, 头两个不仅完成了对坐标的合适处理, 而且还同时完成了state的转换; 只有第三个branch下, 我们下一个iteration还保留在当前的state(因为这个branch对应的是还没有撞墙的情况); 尽管如此, branch3也不是那么简单的, 他用conditional increment这个技巧, 让我们可以直接在branch3这里完成一个对二维index的iteration方向的完全控制.
我们上面讨论过, 有两个结构, 我们用哪个结构的index作为loop var; 这里就看出来用一维index作为loop var的好处了: 不是loop var的那一个结构的index, 往往有更高的自由度. 而我们这里希望要的, 就是二维index的自由度; 我们只要用一维index来loop, 那么矩形内iteration变换的控制其实就变得完全没有那么困难;
这里对r和c的更新, 有点类似离子跃迁那种的更新; 我刚开始拿到这个问题的时候其实想写出来的就是这个算法的, 一套坐标, 可以直接很通用的iterate所有的位置; 但是当时就是没有想到, 以至于后面只能一条线一条线的做, 不同的线之间的坐标是分离的; 这里来看, 也格外体现为什么我认为这个算法其实是这个问题的钦定算法;
有一个问题, 最开始上面依赖d的那个做法, 其实几个branch之间的顺序是很重要的, 但是这里这个算法, branch之间的顺序就没有那么严格, 只要保证撞墙的两个branch在上面就行了;
回过头说上面的那个做法的branch的order的问题:
@Chidong said in Concise Java Solution:
I want to point out that the ordering of these part is important:
if (row >= m) { row = m - 1; col += 2; d = 1 - d;} if (col >= n) { col = n - 1; row += 2; d = 1 - d;} if (row < 0) { row = 0; d = 1 - d;} if (col < 0) { col = 0; d = 1 - d;}If you switch it, you will get an error, like below:
if (row < 0) { row = 0; d = 1 - d;} if (col < 0) { col = 0; d = 1 - d;} if (row >= m) { row = m - 1; col += 2; d = 1 - d;} if (col >= n) { col = n - 1; row += 2; d = 1 - d;}
要知道, 这里判断的几个其实都是撞墙, 为什么撞墙的几个branch之间的顺序还这么重要呢?
其实我也不是很有把握为什么, 还是先跑几个例子看一看. 编程这个东西, 不要搞的太抽象;
参考Stefan这个版本:
for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row -= d;
col += d;
if (row >= m) { row = m - 1; col += 2; d = -d;}
if (col >= n) { col = n - 1; row += 2; d = -d;}
if (row < 0) { row = 0; d = -d;}
if (col < 0) { col = 0; d = -d;}
}
画了一下trace, 只能说这个代码看起来简单, 实际上computation过程还是相当复杂的;
把顺序改错之后, 打印一下坐标的trace, 大概知道问题出在哪里了; 首先, 这种是if chain的写法, 顺序居然有区别(如果是else if的写法, 顺序有关系是正常的, 因为是overriding的关系), 让人很不理解; 唯一的可能性就是几个if之间有交集; 通过trace发现, 是这样的; 比如一个3*3的矩阵, 那么在你走到(2,0)这个位置的时候(自己画trace), 下一个位置是(-1,3), 然后我们要进行撞墙式更新: 发现这里的问题了没有, 这个坐标可以同时触发两个branch(两个坐标同时出界(不可能一个坐标同时出两个界的)), 所以要完成两次更新, 那么两次更新之间的顺序会造成区别还是很正常的;
这个算法的OP自己说什么这个算法很简单, 但是我觉得可能还是个人基础不一样吧, 这个算法无论是idea, 还是implementation, 都有坑, 都不是那么简单, 我认为还是值得学习的;
另外这个算法跟上面提到的最优解法对比的一个一个区别在于, 这里有一个超界回城的操作; 而那个最优解法, 是直接判断等于边界, 而不是已经超出边界. 导致这个差别的一个可能原因是OP的算法完成的是一个类似suffix++的操作: 当前这个位置的操作都已经完成了之后才更新坐标, 就有可能有超界情况; 而且这个更新是一个强制更新(可以看到, 这个更新操作是没有filter控制的); 而最优解法的思路, 则是在当前坐标操作完了之后, 不急着立刻来一个unconditional update, 而是先分析之后, 再决定怎么update, 这样对变量的控制就更加仔细;
这个是跟我的思路很类似的一个思路:
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0) return new int[0];
int h = matrix.length, w = matrix[0].length, id = 0;
int[] res = new int[h*w];
for (int i = 0; i < h+w; i++) {
// find lower bound and upper bound
int lb = (int)Math.max(0, i-w+1), ub = (int)Math.min(i,h-1);
if (i%2 == 0) for (int j = ub; j >= lb; j--) res[id++] = matrix[j][i-j];
else for (int j = lb;j <= ub; j++) res[id++] = matrix[j][i-j];
}
return res;
}
虽然代码写的乱很多, 不过其实背后的思路是几乎一样的, 针对每一个diagonal对应的值, 计算上下边界; 然后判断k的奇偶性, 决定iterate的方向;
注意在边界计算这个方面, 他的理解比我深刻一些, 他找到了一个可以直接用max和min就能解决的计算关系;
还可以写的更短一些:
int[] findDiagonalOrder(int[][] m) {
int[] result = new int[(m.length == 0) ? 0 : m.length * m[0].length];
for (int d = 0, i = 0; i < result.length; d++)
for (int lo = d - min(d, m.length - 1), hi = min(d, m[0].length - 1); lo <= hi; )
result[i++] = ((d & 1) == 0) ? m[d - lo][lo++] : m[d - hi][hi--];
return result;
}
当然, 这么短的版本, 看看就行了, readability已经几乎完全没有了;
一个类似的版本:
public class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[] {};
}
int m = matrix.length;
int n = matrix[0].length;
int index = 0;
int[] diagonal = new int[m * n];
for (int c = 0; c <= m + n - 2; c++) {
if (c % 2 == 0) {
for (int i = Math.min(m - 1, c); i >= Math.max(0, c - n + 1); i--) {
diagonal[index++] = matrix[i][c - i];
}
} else {
for (int i = Math.max(0, c - n + 1); i <= Math.min(m - 1, c); i++) {
diagonal[index++] = matrix[i][c - i];
}
}
}
return diagonal;
}
}
一个稍微次一点的版本, 这个人没有意识到奇偶性来帮助判断iteration方向, 而是直接一个boolean flag做的;
@diaojinggang said in Java solution, easy to understand, O(n), 7ms:
There are two key points.
First, in each path, index row + col == sum. sum is some constant looping from 0 to totalRow + totalCol.
Second, the boundary of row and col is either sum or four edges. Four edges correspond to row == 0 || row == totalRow - 1 || col == 0 || col == totalCol - 1.if{ } block is the only thing we need to figure out. The two tricky parts are "rr = Math.min(sum, r-1)" and "while(rr >= 00 && cc < c)" as I commented in the code.
public class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if(matrix.length == 0)
return new int[0];
int c = matrix[0].length, r = matrix.length;
int[] res = new int[r*c];
boolean flip = true;
int count = 0;
for(int sum = 0; sum <= r + c - 2; sum++){
int rr,cc;
if(flip == true){ // Direction: to up-right
rr = Math.min(sum, r-1); // if before diagonal, rr = sum; else rr = r-1
cc = sum - rr;
while(rr >= 00 && cc < c) // reach matrix upper or right bound
res[count++] = matrix[rr--][cc++];
}
else{ // Direction: to bottom-left
cc = Math.min(sum, c-1); // if before diagonal, cc = sum; else cc = c-1
rr = sum - cc;
while(cc >= 00 && rr < r) // reach matrix bottom or left bound
res[count++] = matrix[rr++][cc--];
}
flip = !flip;
}
return res;
}
}
值得学习的就是他边界处理的方向; 上面的那个做法跟我自己的做法算边界的时候都是统一的算的是x(row), 而这个人的做法不一样, 他在不同的diagonal算的维度不一样, 一个算row, 一个算col; 你可以看到, 他无论算的是rr还是cc, 这两个都是循环的上限(在下面的while循环里面, 被算的这个都是被--的那一个坐标); 反正, 就是知道一下这么个思路吧, 其实本质上确实是没有很大区别的; 他这么写, 估计还是想要找到一个consistency, 因为我们这里有两种需要处理的iteration, 一会儿算上限一会儿算下限他感觉很麻烦, 他就直接统一算上限; 他这样做, 想要统一的其实是increment: 在两种iteration当中, increment都是-1, 相比于之前提到的定制increment, 这个人干脆就是直接让increment完全定死;
Problem Description
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.
Difficulty:Medium
Total Accepted:10.1K
Total Submissions:21.9K
Contributor: nberserk
Companies
google