05 August 2008
跟498的区别是，这个对二维数组的遍历全部是向右上
模拟，维护好坐标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int[] findDiagonalOrder(List<List<Integer>> nums) {
int len = nums.size();
List<Integer> list = new ArrayList<>();
int maxColLen = 0;
int cur;
int curLen;
int curList;
for (int i = 1; i <= len; i++) {
cur = 0;
curLen = i - 1;
while (curLen != -1) {
List<Integer> res = nums.get(curLen);
int r = res.size();
maxColLen = r > maxColLen ? r : maxColLen;
if (cur < r) list.add(res.get(cur));
curLen--;
cur++;
}
}
for (int i = 1; i < maxColLen; i++) {
cur = i;
curList = len - 1;
curLen = len;
while (curLen-- != 0) {
List<Integer> res = nums.get(curList);
if (cur < res.size()) list.add(res.get(cur));
cur++;
curList--;
}
}
return list.stream().mapToInt(i -> i).toArray();
}
}
根据矩形的特点，设行的标号为i，列的标号为j。则对于每一条对角线而言，i + j的值是唯一的。知道这一点之后，就可以按照对角线对nums中的值进行聚类。聚类完毕后，将所有的数值生成一个数组即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int[] findDiagonalOrder(List<List<Integer>> nums) {
int len = 0;
Map<Integer, List<Integer>> map = new TreeMap<>();
for (int i = 0; i < nums.size(); i++) {
len += nums.get(i).size(); // 获取最后要返回的数组的长度，即元素个数
for (int j = 0; j < nums.get(i).size(); j++) {
if (map.containsKey(i + j)) {
map.get(i + j).add(nums.get(i).get(j));
} else {
List<Integer> list = new ArrayList<>();
list.add(nums.get(i).get(j));
map.put(i + j, list);
}
}
}
int[] ans = new int[len];
int index = 0;
for (int key : map.keySet()) { // 遍历map
List<Integer> list = map.get(key);
for (int j = list.size() - 1; j >= 0; j--) { // 根据题目的输出要求确定生成数组中元素的顺序
ans[index] = list.get(j);
index++;
}
}
return ans;
}
}