Я анализирую алгоритм спиральной матрицы. Решение требует ввода матрицы и возврата списка массивов. Это выбранное решение:

 class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0)
        return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 amp;amp; c1 <= c2) {
        for (int c = c1; c <= c2; c  ) ans.add(matrix[r1][c]);
        for (int r = r1   1; r <= r2; r  ) ans.add(matrix[r][c2]);
        if (r1 < r2 amp;amp; c1 < c2) {
            for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
            for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
        }
        r1  ;
        r2--;
        c1  ;
        c2--;
    }
    return ans;
}
  

}

Я просмотрел пространственную сложность на этом сайте, но я не знаю, как применить информацию к этому случаю.

Я просмотрел раздел обсуждения комментариев.

Некоторые говорят, что это O (N) пробел, потому что решение создает список массивов.

Некоторые говорят, что это O (1) пробел, потому что вопрос требует возврата списка массивов. Таким образом, это пространство уже учтено.

Какой из них является истинным?

Определенно O (n)

• Поскольку размер списка ans зависит от размера matrix , мы можем сказать, что это O(1) не ответ. Это потому, что O(1) указывает на постоянное пространство, чего здесь нет.
• Список ans имеет точный размер n = width * height , который позволит ему содержать все элементы в matrix .
• Если наш matrix удвоится в размере, то наш ans также удвоится в размере, поскольку количество элементов удвоилось. Это указывает на линейную зависимость между размером matrix и ans . Тогда мы можем сказать, что наше пространство — это сложность, которая действительно есть O(n) .

O(1) означает, что объем памяти, необходимый для этого алгоритма, не зависит от размера входных данных. Очевидно, что это не тот случай, элемент добавляется в список массивов каждый раз, когда выполняется один из внутренних циклов for. Итак, поскольку алгоритм имеет время выполнения O (MN), он также имеет сложность памяти O (MN), где матрица имеет размер M x N.