题目:给出 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]] 也会被视作正确答案。
感觉这道题目还是非常的有趣,做一个记录
自定义排序函数
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> res;
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
res.push_back({i, j});
}
}
sort(res.begin(), res.end(), [&](vector<int>& a, vector<int>& b){
return abs(a[0] - r0) + abs(a[1] - c0) < abs(b[0] - r0) + abs(b[1] - c0);
});
return res;
}
};
桶排序
注意到方法一中排序的时间复杂度太高。实际在枚举所有点时,我们可以直接按照哈曼顿距离分桶。这样我们就可以实现线性的桶排序。
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);
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));
}
}
vector<vector<int>> ret;
for (int i = 0; i <= maxDist; i++) {
for (auto &it : bucket[i]) {
ret.push_back(it);
}
}
return ret;
}
};
几何法
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<bool>> st(R, vector<bool>(C, false));
st[r0][c0] = true;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
vector<vector<int>> ans;
queue<pair<int, int>> q;
q.push({r0, c0});
while(q.size()){
auto it = q.front();
q.pop();
ans.push_back(vector<int>{it.first, it.second});
for(int i = 0; i< 4; i ++){
int xx = it.first + dx[i], yy = it.second + dy[i];
if(xx >= 0 && xx < R && yy >= 0 && yy < C && !st[xx][yy]){
st[xx][yy] = true;
q.push({xx, yy});
}
}
}
return ans;
}
};