給出 R 行 C 列的矩陣，其中的單元格的整數坐標為 (r, c)，滿足 0 <= r < R 且 0 <= c < C，另外，我們在該矩陣中給出了一個坐標為 (r0, c0) 的單元格，回傳矩陣中的所有單元格的坐標，并按到 (r0, c0) 的距離從最小到最大的順序排，其中，兩單元格(r1, c1) 和 (r2, c2) 之間的距離是曼哈頓距離，|r1 - r2| + |c1 - c2|（你可以按任何滿足此條件的順序回傳答案）
方法一
最簡單的方法，先將資料存在一個二維陣列，再使用 Comparator 對陣列進行排序
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int[][] result = new int[R*C][2];
int k = 0;
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
result[k][0] = i;
result[k][1] = j;
k++;
}
}
Arrays.sort(result, new Comparator<int []>() {
@Override
public int compare(int[] o1, int[] o2) {
int len1 = Math.abs(o1[0] - r0) + Math.abs(o1[1] - c0);
int len2 = Math.abs(o2[0] - r0) + Math.abs(o2[1] - c0);
return len1 - len2;
}
});
return result;
}
}
方法二
使用桶排序，按照距離的大小分組，每組的距離相等（即放入一個桶中），按照距離從小到大的原則，遍歷所有桶，并輸出結果
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int maxDist = Math.max(r0, R - 1 - r0) + Math.max(c0, C - 1 - c0);
List<List<int[]>> bucket = new ArrayList<>();
for(int i = 0; i <= maxDist; i++) {
bucket.add(new ArrayList<>());
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
int d = dist(i, j, r0, c0);
bucket.get(d).add(new int[]{i, j});
}
}
int[][] result = new int[R*C][];
int index = 0;
for (int i = 0; i <= maxDist; i++) {
for (int[] it : bucket.get(i)) {
result[index++] = it;
}
}
return result;
}
public int dist(int r1, int c1, int r2, int c2) {
return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225485.html
標籤：其他