Space 循环外的临时数组的复杂度

Question

我确实遇到过一个著名的面试题，给定一个二维数组，我们需要将数组旋转 90 度，虽然有很多方法可以解决这个问题，但我决定使用一个有效的方法我们做这样的事情的方法。

/*
 * clockwise rotate
 * first reverse up to down, then swap the symmetry 
 * 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 循环中使用的数组可能会使 space 复杂度为 O(n)。如果我只是这样做会怎样：

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

现在是 space 复杂度 O(1) 还是会保持不变？

Answer 1

旋转矩阵之外的唯一 space 是单个元素和指向行的指针，每个都是 O(1)。指针指向 O(N) space 的东西是无关紧要的，因为它是输入的一部分。

请注意，您可以用大约 1/2 的时间进行旋转：不是以两种方式反映整个矩阵，将每个元素移动两次，而是可以旋转每组 4 个元素，其中 A 替换 B，B 替换C，C代替D，D代替A.

Space 循环外的临时数组的复杂度

Space complexity of a temp array that is outside a loop

java

arrays

performance

matrix

space-complexity