问题描述
我正在分析螺旋矩阵 。 该解决方案要求输入矩阵并返回数组列表。 这是选择的解决方案：
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 && 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 && 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）空间，因为问题需要返回数组列表。 因此该空间已被占用。
哪一个是对的？
1楼
绝对O（n）
-
由于List
ans的大小取决于matrix的大小，因此可以说O(1)不是答案。 这是因为O(1)表示恒定的空间 ，在这里不是这种情况。 -
List
ans的确切大小为n = width * height，这将使其包含matrix所有项目。 -
如果
matrix的大小增加了一倍，那么ans大小也会增加一倍，因为项目数量增加了一倍。 这表明matrix的大小与ans之间存在线性关系 。 然后我们可以说我们的空间是复杂度，确实是O(n)。
2楼
O（1）表示此算法所需的内存量不取决于输入的大小。 显然不是这样，每次内部for循环之一迭代时，都会向数组列表中添加一个元素。 因此，由于该算法具有O（MN）运行时间，因此它也具有O（MN）内存复杂度，其中矩阵的大小为M xN。