正文

LeetCode.1030-曼哈顿距离排序矩阵单元格(Matrix Cells in Distance Order)

IP云
IP云V管理员/2 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这是小川的第 384 次更新，第 412 篇原创

01 看题和准备

今天介绍的是 LeetCode 算法题中 Easy 级别的第 246 题（顺位题号是 1030 ）。我们给出一个矩阵，其中R行和C列具有整数坐标 （r，c） 的单元格，其中 0 <= r <R 且 0 <= c <C 。

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

返回矩阵中所有单元格的坐标，按照它们从 （r0，c0） 到最小距离到最大距离的距离进行排序。这里，两个单元格 （r1，c1） 和 （r2，c2） 之间的距离是曼哈顿距离， |r1 - r2| + |c1 - c2| 。（你可以按任何满足此条件的顺序返回答案。）

例如：

输入：R = 1，C = 2，r0 = 0，c0 = 0

输出：[[0,0]，[0,1]]

说明：从 （r0，c0） 到其他单元格的距离为：[0,1]

输入：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]] 也将被接受为正确。

输入：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 <= R <= 100

  • 1 <= C <= 100

  • 0 <= r0 <R

  • 0 <= c0 <C

02 第一种解法

题目的意思是根据给定范围的R和C组成一个二维数组，算出所有 (r,c) 到 (r0,c0) 的曼哈顿距离，根据曼哈顿距离的大小来排序二维数组里面的元素。

因此，我们只需要做两件事情，先将二维数组中的元素初始化好，再根据每个元素到到 (r0,c0) 的曼哈顿距离来排序数组元素。对于排序，我们借助 Arrays 的 sort 方法，在 sort 方法第二个参数里，实现 Comparator 接口，重写其 compare 方法，排序规则依据两点的曼哈顿距离大小来定，最后输出排序后的数组即可。 

public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {

    int[][] matrix = new int[R*C][2];

    int index = 0;

    for (int i=0; i<R; i++) {

        for (int j=0; j<C; j++) {

            matrix[index][0] = i;

            matrix[index][1] = j;

            index++;

        }

    }

    Arrays.sort(matrix, new Comparator<int[]>() {

        @Override

        public int compare(int[] a, int[] b) {

            int distance = Math.abs(a[0]-r0)+Math.abs(a[1]-c0);

            int distance2 = Math.abs(b[0]-r0)+Math.abs(b[1]-c0);

            return distance - distance2;

        }

    });

    return matrix;

}

03 第二种解法

思路和第一种解法一样，只是将排序算法优化了，时间复杂度变成了 O(N) ，其中 N 代表 R*C ，使用的是计数排序算法，但是这里用到的排序算法和我们之前使用过的排序算法稍有不同，属于进阶版，本周会抽时间单独写一篇介绍计数排序算法的文章，这里就不展开细讲了。 

public int[][] allCellsDistOrder2(int R, int C, int r0, int c0) {

    int[][] matrix = new int[R*C][2];

    int[] count = new int[R + C];

    for (int i = 0; i < R; i++) {

        for (int j = 0; j < C; j++) {

            int dis = Math.abs(i - r0) + Math.abs(j - c0);

            count[dis + 1]++;

        }

    }

    for (int i = 1; i < count.length; i++) {

        count[i] += count[i - 1];

    }

    for (int r = 0; r < R; r++) {

        for (int c = 0; c < C; c++) {

            int dis = Math.abs(r - r0) + Math.abs(c - c0);

            matrix[count[dis]] = new int[] {r, c};

            count[dis]++;

        }

    }

    return matrix;

}

04 小结

算法专题目前已连续 日更超过七个月 ，算法题文章 252 +篇，公众号对话框回复【 数据结构与算法 】、【 算法 】、【 数据结构 】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

相关阅读

目录[+]