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

[[0,1],[1,1],[0,0],[1,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) {

}
};
``````

``````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;
}
};
``````

``````    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
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。