LeetCode每日一题--1030. 距离顺序排列矩阵单元格(桶排序)

题目:跳转至 1030. 距离顺序排列矩阵单元格
给出 R 行 C 列的矩阵,其中的单元格的整数坐标为 (r, c),满足 0 <= r < R 且 0 <= 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 <= R <= 100
  • 1 <= C <= 100
  • 0 <= r0 < R
  • 0 <= c0 < C
class Solution { 
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) { 
        
    }
};

思路:
《LeetCode每日一题--1030. 距离顺序排列矩阵单元格(桶排序)》

因为算距离是行之间差的绝对值与列之间差的绝对值之和,直接填表格,就发现规律。差值1的都在目标位置的上下左右,差值234的分别成菱形往外扩一层。然后我就又有点无从下手。如何把差值1遍历完后继续遍历差值2,差值3。

看题解,方法一又惊呆我,sort愿称为万能!
方法二的桶排序要记小本本,后面周末统一补充一下吧。
方法三,思路差不多,但是就很厉害。首先dr,dc分别对应右下角,左下角,左上角,右上角。但是循环时先row0-1,则获取到其上顶点的值,按dr,dc的循环,获取到上顶点右下即原节点左边的值,接着左边的值的左下角即原节点下端,再是下端值的右上即原节点的左侧,接着返回起点到row0继续减一开始下一层循环,太过优秀,中间注意下判断条件即可。

class Solution { 
public:
    const int dr[4] = { 1, 1, -1, -1};
    const int dc[4] = { 1, -1, -1, 1};
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) { 
        int maxDist = max(r0, R - 1 - r0) + max(c0, C - 1 - c0);
        vector<vector<int>> ret;
        int row = r0, col = c0;
        ret.push_back({ row, col});
        for (int dist = 1; dist <= maxDist; dist++) { 
            row--;
            for (int i = 0; i < 4; i++) { 
                while ((i % 2 == 0 && row != r0) || (i % 2 != 0 && col != c0)) { 
                    if (row >= 0 && row < R && col >= 0 && col < C) { 
                        ret.push_back({ row, col});
                    }
                    row += dr[i];
                    col += dc[i];
                }
            }
        }
        return ret;
    }
};

方法二的桶排序:

class Solution { 
public:
    int dist(int r1, int c1, int r2, int c2) {   //计算返回曼哈顿距离
        return abs(r1 - r2) + abs(c1 - c2);
    }
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) { 
        int maxDist = max(r0, R - 1 - r0) + max(c0, C - 1 - c0);
        vector<vector<vector<int>>> bucket(maxDist + 1);  //根据最大距离初始化桶的个数
        //遍历,根据距离把(r,c) 分别放入不同的桶中存储
        for (int i = 0; i < R; i++) {  
            for (int j = 0; j < C; j++) { 
                int d = dist(i, j, r0, c0);
                vector<int> tmp = { i, j};
                bucket[d].push_back(move(tmp));  //move会无条件将参数转为右值,在对象拷贝时可以减少资源创建和释放
            }
        }
        vector<vector<int>> ret;
        for (int i = 0; i <= maxDist; i++) {   //把桶中元素都按桶顺序排列给出
            for (auto &it : bucket[i]) { 
                ret.push_back(it);
            }
        }
        return ret;
    }
};

这里题目里对同等距离的坐标输出不做要求,桶排序借用菜鸟教程里面的图再深入一点点。
《LeetCode每日一题--1030. 距离顺序排列矩阵单元格(桶排序)》
《LeetCode每日一题--1030. 距离顺序排列矩阵单元格(桶排序)》
直接依照图片内容写的,比较偷懒。

    vector<int> bucketSort(vector<int> nums){ 
        int maxnum=max_element(nums.begin(),nums.end())-nums.begin();
        vector<vector<int>> bucket(nums[maxnum]%10+1);  //确定桶的数量
        for(auto x:nums) //放入桶中
            bucket[x%10].push_back(x);
        for(auto tmp:bucket)  //桶内排序
            sort(tmp.begin(),tmp.end());
        vector<int> res;
        for(auto tmp:bucket){   //合并
            for(auto x:tmp){ 
                res.push_back(x);
            }
        }
        return res;
    }
    原文作者:七七不是七七七七
    原文地址: https://blog.csdn.net/qq_39295095/article/details/109758859
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞