java 我正在解决leetcode问题编号885(螺旋矩阵III),一切似乎都是正确的,但它显示时间限制超过

wfsdck30  于 2023-03-28  发布在  Java
关注(0)|答案(1)|浏览(184)

发生过一次,我也得到了时间限制超过错误。不能得到如果一切都是正确的,为什么这是错误。还没有研究过时间复杂度,但如果有人能简要地解释一下,那就太好了。下面是问题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++;
    }
}

你能告诉我哪里出了问题吗?哪一行可以改进以提高时间复杂度?同样的方法正在运行,但在几次修改之前给出了错误的答案。
感谢您抽出时间:)

uqxowvwt

uqxowvwt1#

对于第二个示例输入,您的代码将进入无限循环:

rows = 5, cols = 6, rStart = 1, cStart = 4

它在第一次外循环和第三次内循环中出错:在那里,算法向东走,但走得太远了,加上坐标{2, 2},然后第四个循环将从该点垂直向前移动。但这意味着算法不会访问{1, 3},使“圆圈”越来越大,但永远不会达到所需的访问细胞计数,因为这一点永远不会被访问。
仔细看看算法,你永远不应该用两个步骤来改变rStartrEndcStartcEnd变量中的任何一个。我明白你这样做是为了补偿对这些变量的临时相反调整,这反过来又是处理“弯道”所必需的。但这可以用更好的方式来完成,其还解决了以下问题:

  • 让你的内部循环提前一次停止,这样它们就不会覆盖最后的“角落”单元格--把它留给下一个内部循环来覆盖
  • 仅用一个单元调整4个相关变量。

代码中的另一个问题与变量count有关:每次运行时都应将其重置为零,否则您将面临上一次运行的值成为下一次运行的起始值的风险。
以下是更正:

class Solution {
    int count = 0;
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] ans = new int[rows*cols][2];

        count = 0; // Reset!

        int rEnd = rStart+1;
        int cEnd = cStart+1;

        while(count<rows*cols){
            for(int i = cStart; i < cEnd && count<rows*cols; i++){ // Stop one iteration earlier
                if(i<cols && i>=0 && rStart>=0 && rStart<rows) addToAns(ans, rStart, i);
            }
            cStart--; // One unit only
            for(int i = rStart; i < rEnd && count<rows*cols; i++){ // Stop one iteration earlier
                if(i<rows && i>=0 && cEnd>=0 && cEnd<cols) addToAns(ans, i, cEnd);
            }
            rStart--; // One unit only
            for(int i = cEnd; i > cStart && count<rows*cols; i--) { // Stop one iteration earlier
                if(i>=0 && i<cols && rEnd>=0 && rEnd<rows) addToAns(ans, rEnd, i);
            }
            cEnd++; // One unit only
            for(int i = rEnd; i > rStart && count<rows*cols; i--){ // Stop one iteration earlier
                if(i>=0 && i<rows && cStart>=0 && cStart<cols) addToAns(ans, i, cStart);
            }
            rEnd++;  // One unit only
        }
        return ans;
    }

    void addToAns(int[][] ans, int row, int col){
        ans[count][0] = row;
        ans[count][1] = col;
        count++;
    }
}

其他备注

虽然这解决了眼前的问题,但有几种方法可以改进此代码:

  • addAns本身可以验证坐标是否有效,因此您只需将四个if条件替换为一个。
  • 通过仔细的循环条件,你甚至可以避免用一个单独的if来检查坐标的有效性。你可以避免在应该遍历的线完全超出范围时启动一个内部循环。这可以保存大量的迭代。
  • 应该不需要有一个非本地变量count。要实现这一点,将ans[count]传递给addAns而不是ans。然后您还可以同时递增count

以下是考虑到这些评论的情况:

class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int size = rows*cols;
        int[][] ans = new int[size][2];
        int rEnd = rStart+1;
        int cEnd = cStart+1;
        int count = 0;

        while (true) { // We will exit the loop with a return statement
            if (rStart >= 0) { // Skip entirely if row out of range
                for(int c = Math.max(cStart, 0); c < cEnd; c++){ // Stop one iteration earlier
                    addToAns(ans[count++], rStart, c);
                    if (count >= size) return ans;
                }
            }
            if (cStart >= 0) cStart--;  // One unit only and don't move it when already out of range
            if (cEnd < cols) { // Skip entirely if column out of range
                for(int r = Math.max(0, rStart); r < rEnd; r++){
                    addToAns(ans[count++], r, cEnd);
                    if (count >= size) return ans;
                }
            }
            if (rStart >= 0) rStart--;  // One unit only and don't move it when already out of range
            if (rEnd < rows) { // Skip entirely if row out of range
                for(int c = Math.min(cEnd, cols - 1); c > cStart; c--) { // Stop one iteration earlier
                    addToAns(ans[count++], rEnd, c);
                    if (count >= size) return ans;
                }
            }
            if (cEnd < cols) cEnd++;  // One unit only and don't move it when already out of range
            if (cStart >= 0) { // Skip entirely if column out of range
                for(int r = Math.min(rEnd, rows - 1); r > rStart; r--){ // Stop one iteration earlier
                    addToAns(ans[count++], r, cStart);
                    if (count >= size) return ans;
                }
            }
            if (rEnd < rows) rEnd++;  // One unit only and don't move it when already out of range
        }
    }

    void addToAns(int[] ans, int row, int col){
        ans[0] = row;
        ans[1] = col;
    }
}

相关问题