Easy

题目描述

给你四个整数 row、cols、rCenter 和 cCenter。有一个 rows x cols 的矩阵，你在坐标为 (rCenter, cCenter) 的单元格上。

返回矩阵中的所有单元格的坐标，并按它们与 (rCenter, cCenter) 的距离从最小到最大的顺序排序。你可以返回满足此条件的任何顺序的答案。

两个单元格 (r1, c1) 和 (r2, c2) 之间的距离为 |r1 - r2| + |c1 - c2|。

示例 1：

输入：rows = 1, cols = 2, rCenter = 0, cCenter = 0
输出：[[0,0],[0,1]]
解释：从 (0, 0) 到其他单元格的距离为：[0,1]

示例 2：

输入：rows = 2, cols = 2, rCenter = 0, cCenter = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (0, 1) 到其他单元格的距离为：[0,1,1,2]
答案 [[0,1],[1,1],[0,0],[1,0]] 也会被视为正确答案。

示例 3：

输入：rows = 2, cols = 3, rCenter = 1, cCenter = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (1, 2) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足条件的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

  • 1 <= rows, cols <= 100
  • 0 <= rCenter < rows
  • 0 <= cCenter < cols

解题思路

这道题要求按曼哈顿距离排序矩阵中的所有单元格。曼哈顿距离计算公式为 |r1 - r2| + |c1 - c2|。

解法思路：

  1. 直接排序法：遍历矩阵所有单元格，计算每个单元格到中心点的距离，然后按距离排序。这是最直观的方法，时间复杂度为 O(RC·log(RC))。

  2. 桶排序法：由于距离的范围是有限的（最大距离不超过 rows + cols - 2），我们可以使用桶排序优化。先计算所有单元格的距离，然后按距离分组，最后按距离从小到大输出各组的单元格。

  3. BFS遍历法：从中心点开始进行广度优先搜索，按层级遍历，每一层的单元格距离相同。这种方法不需要排序，天然按距离顺序输出。

推荐解法是桶排序法，它在这种场景下效率最高，时间复杂度仅为 O(RC)，空间复杂度也很优秀。

核心思路是：

  1. 创建距离桶，最大距离为 maxDist = max(rCenter, rows-1-rCenter) + max(cCenter, cols-1-cCenter)
  2. 遍历所有单元格，计算距离并放入对应桶中
  3. 按距离顺序输出所有桶中的单元格

代码实现

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);
        vector<vector<vector<int>>> buckets(maxDist + 1);
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int dist = abs(r - rCenter) + abs(c - cCenter);
                buckets[dist].push_back({r, c});
            }
        }
        
        vector<vector<int>> result;
        for (int i = 0; i <= maxDist; i++) {
            for (auto& cell : buckets[i]) {
                result.push_back(cell);
            }
        }
        
        return result;
    }
};

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        max_dist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter)
        buckets = [[] for _ in range(max_dist + 1)]
        
        for r in range(rows):
            for c in range(cols):
                dist = abs(r - rCenter) + abs(c - cCenter)
                buckets[dist].append([r, c])
        
        result = []
        for bucket in buckets:
            result.extend(bucket)
        
        return result

public class Solution {
    public int[][] AllCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int maxDist = Math.Max(rCenter, rows - 1 - rCenter) + Math.Max(cCenter, cols - 1 - cCenter);
        List<List<int[]>> buckets = new List<List<int[]>>();
        
        for (int i = 0; i <= maxDist; i++) {
            buckets.Add(new List<int[]>());
        }
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int dist = Math.Abs(r - rCenter) + Math.Abs(c - cCenter);
                buckets[dist].Add(new int[] {r, c});
            }
        }
        
        List<int[]> result = new List<int[]>();
        for (int i = 0; i <= maxDist; i++) {
            result.AddRange(buckets[i]);
        }
        
        return result.ToArray();
    }
}

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
    const maxDist = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter);
    const buckets = Array.from({length: maxDist + 1}, () => []);
    
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            const dist = Math.abs(r - rCenter) + Math.abs(c - cCenter);
            buckets[dist].push([r, c]);
        }
    }
    
    const result = [];
    for (let i = 0; i <= maxDist; i++) {
        result.push(...buckets[i]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
桶排序法O(RC)O(RC)
直接排序法O(RC·log(RC))O(RC)
BFS遍历法O(RC)O(RC)

其中 R 为矩阵行数，C 为矩阵列数。桶排序法是最优解法，避免了排序的额外时间开销。

相关题目