我正在分析螺旋矩阵algorithm。该解决方案要求输入矩阵并返回数组列表。这是选择的解决方案:
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;
}
}
我在这个site查找了空间复杂性,但我不知道如何将信息应用于此案例。
我查看了评论的讨论部分。
有人说它是O(N)空间,因为解决方案创建了一个数组列表。
有人说它是O(1)空间,因为问题需要返回数组列表。因此,空间已被考虑在内。
哪一个是真的?
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×N。