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

Question

我确实遇到过一个著名的面试问题，其中给定了一个 2D 数组，我们需要将数组旋转 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*/

My code for above approach is:

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) 空间的某个内容是无关紧要的，因为它是输入的一部分。

请注意，您可以在大约 1/2 的时间内完成旋转:您可以旋转每组 4 个元素，其中 A 替换 B，B 替换 C，而不是以两种方式反射(reflect)整个矩阵，将每个元素移动两次， C 替换 D，D 替换 A。