「每日LeetCode」2020年11月17日

本文最后更新于：2023年3月19日 晚上

Lt1030. 距离顺序排列矩阵单元格，桶排序，BFS

1030. 距离顺序排列矩阵单元格

给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）
 示例 1：

1
2
3
输入：R = 1, C = 2, r0 = 0, c0 = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

1
2
3
4
输入：R = 2, C = 2, r0 = 0, c0 = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

1
2
3
4
输入：R = 2, C = 3, r0 = 1, c0 = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

  1. 1 <= R <= 100
  2. 1 <= C <= 100
  3. 0 <= r0 < R
  4. 0 <= c0 < C

思路

直接排序

先生成一个所有点数组，再根据曼哈顿距离升序排序即可。

桶排序

使用桶排序，节省了排序的步骤。根据距离在 map 中放置元素，再遍历 map，默认就是从最小到最大距离来遍历。直接将对应的 value 连接上结果数组中即可。

BFS

1
2
3
4
5
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5

BFS 思想，曼哈顿距离如以上矩阵所示。使用一个矩阵记录当前点是否已遍历过，将当前点加入结果数组，然后将当前点上下左右的点加入队列，并设为已访问过。加入结果数组的顺序根据 BFS 过程，一定符合曼哈顿距离从小到大的顺序。

解答

直接排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}
 */
var allCellsDistOrder = function (R, C, r0, c0) {
  const points = [];
  points.push(new Array(R * C));
  let index = 0;
  for (let x = 0; x < R; x++) {
    for (let y = 0; y < C; y++) {
      points[index++] = [x, y];
    }
  }
  points.sort(
    (a, b) =>
      Math.abs(r0 - a[0]) +
      Math.abs(c0 - a[1]) -
      (Math.abs(r0 - b[0]) + Math.abs(c0 - b[1]))
  );
  return points;
};

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}
 */
var allCellsDistOrder = function (R, C, r0, c0) {
  const getDistance = (point) =>
    Math.abs(r0 - point[0]) + Math.abs(c0 - point[1]);
  const map = {};
  for (let x = 0; x < R; x++) {
    for (let y = 0; y < C; y++) {
      const distance = getDistance([x, y]);
      if (map[distance]) map[distance].push([x, y]);
      else map[distance] = [[x, y]];
    }
  }
  return Object.values(map).reduce((a, b) => a.concat(b), []);
};

BFS

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
35
36
/**
 * @param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}
 */
var allCellsDistOrder = function (R, C, r0, c0) {
  const visited = Array.from(new Array(R)).map(() => new Array(C).fill(0));
  const queue = [[r0, c0]];
  visited[r0][c0] = 1;
  const res = [];
  while (queue.length) {
    const point = queue.shift();
    const x = point[0],
      y = point[1];
    res.push(point);
    if (x - 1 >= 0 && !visited[x - 1][y]) {
      queue.push([x - 1, y]);
      visited[x - 1][y] = 1;
    }
    if (y - 1 >= 0 && !visited[x][y - 1]) {
      queue.push([x, y - 1]);
      visited[x][y - 1] = 1;
    }
    if (x + 1 < R && !visited[x + 1][y]) {
      queue.push([x + 1, y]);
      visited[x + 1][y] = 1;
    }
    if (y + 1 < C && !visited[x][y + 1]) {
      queue.push([x, y + 1]);
      visited[x][y + 1] = 1;
    }
  }
  return res;
};