题目描述
给出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
题解
先将所有的单元格的坐标放入向量v，再声明一个整形数组len用来保存每个单元格到（r0，c0）的距离，len和v的下标是一一对应的。将所有元素都放入数组后，再进行升序排序，这里要把数组len和向量v同时排序。这里我用的是快速排序方法。
代码如下
class Solution {
public:
void sort(vector< vector<int> > &v, int len[], int low, int high)
{
if(high > 100) //单元格数量大于100，用快速排序
Qsort(v, len, low, high);
else //否则用插入排序
Insertsort(v, len, high);
}
void Qsort(vector< vector<int> > &v, int len[], int low, int high) //快速排序
{
int pivot;
if(low < high)
{
pivot = Part(v, len, low, high); //将v和len一分为二
Qsort(v, len, low, pivot-1); //对低子表递归排序
Qsort(v, len, pivot+1, high); //对高子表递归排序
}
}
int Part(vector< vector<int> > &v, int len[], int low, int high) //先选取当中的一个关键字（pivot），然后想办法将它放到一个位置，
使得它左边的值都比它小，右边的值都比它大
{
vector<int> temp(2);
int pivotkey = len[low]; //用子表的第一个元素作关键字
int tmp;
while(low < high) //从表的两端交替向中间扫描
{
while(low < high && len[high] >= pivotkey)
{
high--;
}
//将比pivotkey小的元素换到低位
temp = v[low];
v[low] = v[high];
v[high] = temp;
tmp = len[low];
len[low] = len[high];
len[high] = tmp;
while(low < high && len[low] <= pivotkey)
{
low++;
}
//将比pivotkey大的元素换到高位
temp = v[low];
v[low] = v[high];
v[high] = temp;
tmp = len[low];
len[low] = len[high];
len[high] = tmp;
}
return low; //返回pivotkey所在的位置
}
void Insertsort(vector< vector<int> > &v, int len[], int high) //直接插入排序
{
int i,j;
int t;
vector<int> temp(2);
for(i = 1; i <= high; i++)
{
if(len[i-1] > len[i]) //需要把len[i]插入数组
{
t = len[i]; //设置哨兵
temp = v[i];
for(j = i-1; j>=0 && len[j] >= t; j--) //记录后移
{
len[j+1] = len[j];
v[j+1] = v[j];
}
len[j+1] = t; //插入到正确位置
v[j+1] = temp;
}
}
}
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> v;
vector<int> temp(2);
int len[R*C] = {0};
int i, j, templen,k;
for(i = 0; i < R; i++)
{
temp[0] = i;
for(j = 0; j < C; j++)
{
temp[1] = j;
v.push_back(temp);
len[j+i*C] = abs(temp[0]-r0) + abs(temp[1]-c0);
}
}
sort(v,len,0,C*R-1);
return v;
}
};
结果
这道题我提交了n多次，主要问题有两个：下标越界和超时。
- 下标越界
下标越界问题出在插入排序的循环条件判断中【没错，又是这个for循环】
最初的代码
for(k = i - 1; len[k] >= templen && k >= 0; k--)
错误提示
runtime error: index -1 out of bounds for type 'int [*]' (solution.cpp)
这个提示说明k会减小到-1，进行条件判断时会判断 len[-1] >=templen，而len[-1]是不存在的元素，于是下标越界就发生了。
改进代码
for(k = i - 1; k >= 0; k--)
{
if(len[k] >= templen)
{
len[k+1] = len[k];
v[k+1] = v[k];
}
else
break;
}
这段代码将一部分条件判断放入了循环内，这样就避免了下标越界。
-
超时
最初的代码用的是直接插入排序【时间复杂度为O(n^2)】。因为显示超时，我就加入了快速排序【时间复杂度为O(nlogn)】。当单元格的数量大于100时，采用快速排序，否则就用直接插入排序。
最后po一下结果吧，其实挺慢的【苦笑
通过结果
