发生过一次,我也得到了时间限制超过错误。不能得到如果一切都是正确的,为什么这是错误。还没有研究过时间复杂度,但如果有人能简要地解释一下,那就太好了。下面是问题link。下面是我的代码:
class Solution {
int count = 0;
public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
int[][] ans = new int[rows*cols][2];
int rEnd = rStart+1;
int cEnd = cStart+1;
while(count<rows*cols){
for(int i = cStart; i<=cEnd && count<rows*cols; i++){
if(i<cols && i>=0 && rStart>=0 && rStart<rows) addToAns(ans, rStart, i);
}
cStart = cStart - 2;
rStart++;
for(int i = rStart; i<=rEnd && count<rows*cols; i++){
if(i<rows && i>=0 && cEnd>=0 && cEnd<cols) addToAns(ans, i, cEnd);
}
rStart = rStart-2;
cEnd--;
for(int i = cEnd; i>= cStart && count<rows*cols; i--){
if(i>=0 && i<cols && rEnd>=0 && rEnd<rows) addToAns(ans, rEnd, i);
}
cEnd = cEnd+2;
rEnd++;
for(int i = rEnd; i>= rStart && count<rows*cols; i--){
if(i>=0 && i<rows && cStart>=0 && cStart<cols) addToAns(ans, i, cStart);
}
rEnd = rEnd + 2;
cStart++;
}
return ans;
}
void addToAns(int[][] ans, int row, int col){
ans[count][0] = row;
ans[count][1] = col;
count++;
}
}
你能告诉我哪里出了问题吗?哪一行可以改进以提高时间复杂度?同样的方法正在运行,但在几次修改之前给出了错误的答案。
感谢您抽出时间:)
1条答案
按热度按时间uqxowvwt1#
对于第二个示例输入,您的代码将进入无限循环:
它在第一次外循环和第三次内循环中出错:在那里,算法向东走,但走得太远了,加上坐标
{2, 2}
,然后第四个循环将从该点垂直向前移动。但这意味着算法不会访问{1, 3}
,使“圆圈”越来越大,但永远不会达到所需的访问细胞计数,因为这一点永远不会被访问。仔细看看算法,你永远不应该用两个步骤来改变
rStart
,rEnd
,cStart
,cEnd
变量中的任何一个。我明白你这样做是为了补偿对这些变量的临时相反调整,这反过来又是处理“弯道”所必需的。但这可以用更好的方式来完成,其还解决了以下问题:代码中的另一个问题与变量
count
有关:每次运行时都应将其重置为零,否则您将面临上一次运行的值成为下一次运行的起始值的风险。以下是更正:
其他备注
虽然这解决了眼前的问题,但有几种方法可以改进此代码:
addAns
本身可以验证坐标是否有效,因此您只需将四个if
条件替换为一个。if
来检查坐标的有效性。你可以避免在应该遍历的线完全超出范围时启动一个内部循环。这可以保存大量的迭代。count
。要实现这一点,将ans[count]
传递给addAns
而不是ans
。然后您还可以同时递增count
。以下是考虑到这些评论的情况: