• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

互联网 diligentman 6天前 8次浏览

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


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/matrix-cells-in-distance-order/

题目


给出 RC 列的矩阵,其中的单元格的整数坐标为 (r, c),满足 0 <= r < R0 <= c < C

另外,我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。

返回矩阵中的所有单元格的坐标,并按到 (r0, c0) 的距离从最小到最大的顺序排,其中,两单元格(r1, c1)(r2, c2) 之间的距离是曼哈顿距离,|r1 - r2| + |c1 - c2|。(你可以按任何满足此条件的顺序返回答案。)

示例 1:

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

示例 2:

输入: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:

输入: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

解题思路


思路:直接排序、桶排序、BFS

先审题,本题题意弄清楚后,就会有直观的解法。

首先题目给出的

R

R

R

C

C

C 列的矩阵,其中:

  • 矩阵中的单元格坐标为

    (

    r

    ,

    c

    )

    (r, c)

    (r,c),这里

    0

    r

    <

    R

    0 leq r < R

    0r<R

    0

    c

    <

    C

    0 leq c < C

    0c<C

题目中还给出一个坐标为

(

r

0

,

c

0

)

(r0, c0)

(r0,c0) 的单元格。(这个单元格在给定的矩阵内,其实就是从矩阵中挑一个坐标)

现在题目要求的是返回矩阵所有单元格坐标,要求单元格坐标到

(

r

0

,

c

0

)

(r0, c0)

(r0,c0) 的距离大小顺序排列。其中这里的距离指的是曼哈顿距离。

在这里,假设存在两单元格

(

r

1

,

c

1

)

(r1, c1)

(r1,c1)

(

r

2

,

c

2

)

(r2, c2)

(r2,c2),那么两者之间的曼哈顿距离就是:

d

(

i

,

j

)

=

r

1

r

2

+

c

1

c

2

d(i, j) = |r1 – r2| + |c1 – c2|

d(i,j)=r1r2+c1c2

直接排序

那么,这里其实就是排序的问题。只不过排序规则是:根据点到点之间的曼哈顿距离大小进行排序

这里,先说下直接排序的方法:

  • 先将矩阵中所有的单元格坐标都存储在列表中;
  • 然后进行排序,这里的排序规则则改成按照所有单元格坐标到给定的

    (

    r

    0

    ,

    c

    0

    )

    (r0, c0)

    (r0,c0) 单元格的曼哈顿距离大小升序排序。

具体的代码实现如下。

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        # 先将所有的坐标都放到列表中
        res = [(r, c) for r in range(R) for c in range(C)]
        # 改变排序的规则,根据曼哈顿距离的大小排序
        res.sort(key=lambda x: abs(x[0] - r0) + abs(x[1] - c0))
        return res

桶排序

上面的直接排序的思路,首先需要先将所有的坐标点都放到列表中,然后再进行排序,时间复杂度较高。

这里我们可以使用桶排序,根据曼哈顿距离,将坐标放到对应的桶中。具体的思路如下:

  • 首先先求得坐标之间的最大曼哈顿距离;(见示例,坐标之间的距离列表中,可能存在相同的距离,但会有一个最大的距离。)
  • 根据求得的最大曼哈顿距离,确定桶的数量。根据曼哈顿距离分桶,相同的放到同个桶中;
  • 最后,将桶中的坐标,根据距离大小添加到结果列表中。

具体的代码实现如下。

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        def get_d(r, c, r0, c0):
            """求曼哈顿距离
            """
            return abs(r-r0) + abs(c-c0)
        
        # 确定曼哈顿距离的最大值,进而确定桶数量
        max_d = max(r0, R - 1 - r0) + max(c0, C - 1 - c0)
        # 初始化桶,遍历将坐标放入根据曼哈顿距离放到对应的桶中
        bucket = {}
        for r in range(R):
            for c in range(C):
                d = get_d(r, c, r0, c0)
                if d not in bucket:
                    bucket[d] = []
                bucket[d].append([r, c])
        
        # 将桶中元素添加到结果列表中
        res = []
        for i in range(max_d+1):
            res.extend(bucket[i])
        
        return res

BFS

这里,我们也可以用 BFS 的思路来实现。具体的思路如下:

  • 以给定的坐标

    (

    r

    0

    ,

    c

    0

    )

    (r0, c0)

    (r0,c0) 作为起始点,出队,开始往四周的坐标点进行扩散;

  • 扩散时,需要注意边界问题,以及是否被扩散访问过;
  • 这里入队列,是根据曼哈顿距离从小到大进行入队。

具体的代码实现如下。

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        # 四个方位
        dire = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        
        # 标记是否已经被扩散访问过
        signed = [[False] * C for _ in range(R)]
        
        queue = collections.deque()
        # 添加起始点
        queue.append([r0, c0])
        # 标记已扩散
        signed[r0][c0] = True

        res = []
        while queue:
            # 出列,准备扩散
            cur =  queue.popleft()
            res.append(cur)

            r, c = cur
            # 开始往四周扩散
            for _ in range(4):
                for i, j in dire:
                    nr = r + i
                    nc = c + j
                    # 注意边界,以及是否被扩散访问过
                    if 0 <= nr < R and 0 <= nc < C and not signed[nr][nc]:
                        queue.append([nr, nc])
                        signed[nr][nc] = True
            
        return res

欢迎关注


公众号 【书所集录】


如有错误,烦请指出,欢迎指点交流。


喜欢 (0)