LeetCode-1030

题目

结果

代码

ARRAYS.SORT

根据曼哈顿距离直接快排

class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] ans = new int[R * C][2];
        initialize(ans, R, C);
        Arrays.sort(ans, Comparator.comparingInt(o -> distance(r0, c0, o[0], o[1])));
        return ans;
    }

    private int distance(int r0, int c0, int r, int c) {
        return abs(r0 - r) + abs(c0 - c);
    }

    private int abs(int x) {
        return x >= 0 ? x : -x;
    }

    private void initialize(int[][] arr, int R, int C) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                arr[i * C + j][0] = i;
                arr[i * C + j][1] = j;
            }
        }
    }
}

桶排序

对于值域已知的序列，可以使用桶排序加速。这道题可以用曼哈顿距离作为分桶的依据，而且桶内不用再继续排序，一步到位。

class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        // 若干个桶的集合
        List<List<int[]>> buckets = new ArrayList<>();
        // 桶的个数
        int nums = Math.max(r0, R - r0 - 1) + Math.max(c0, C - c0 - 1) + 1;
        // 添加nums个桶到集合里
        for (int i = 0; i < nums; i++) {
            buckets.add(new ArrayList<>());
        }

        // 根据曼哈顿距离，把每个元素添加到不同的桶里
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                buckets.get(distance(r0, c0, i, j)).add(new int[]{i, j});
            }
        }

        int[][] ans = new int[R * C][2];
        int index = 0;
        for (var bucket : buckets) {
            for (var rc : bucket) {
                ans[index] = rc;
                index++;
            }
        }

        return ans;
    }

    private int distance(int r0, int c0, int r, int c) {
        return abs(r0 - r) + abs(c0 - c);
    }

    private int abs(int x) {
        return x >= 0 ? x : -x;
    }
}

复杂度（桶排序的算法）

时间复杂度：O（n）

空间复杂度：O（n），n为元素个数R×C