循环外的临时数组的空间复杂度

Question

我确实遇到了一个著名的面试问题，在该问题中，我们获得了2D数组，需要将数组旋转90度，尽管有很多解决方法，但我决定采用一种有效的方法我们做这样的事情。

/ **顺时针旋转*首先反转从上到下，然后交换对称* 1 2 3 7 8 9 7 4 1* 4 5 6 => 4 5 6 => 8 5 2* 7 8 9 1 2 3 9 6 3* /

我上述方法的代码是：

public void rotate(int[][] matrix) {
    int s = 0, e = matrix.length - 1;
    while(s < e){
        int[] temp = matrix[s];
        matrix[s] = matrix[e];
        matrix[e] = temp;
        s++; e--;
    }

    for(int i = 0; i < matrix.length; i++){
        for(int j = i+1; j < matrix[i].length; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

我在这里主要担心的是，我在第一个while循环内使用的数组可能会使空间复杂度O（n）。如果我只是这样做，该怎么办：

int[] temp;
while( s < e ){
   temp = matrix[s];
}

现在是空间复杂度O（1）还是保持不变？

Answer 1

您要旋转的矩阵之外的唯一空间是单个元素和一个指向行的指针，每个指针均为O（1）。指针指向O（N）空间的某些内容无关紧要，因为它是输入的一部分。