时间戳

首页 > 解决方案 > 返回数组列表的算法的空间复杂度是多少？

java - 返回数组列表的算法的空间复杂度是多少？

问题描述

我正在分析螺旋矩阵算法。该解决方案要求输入一个矩阵并返回一个数组列表。这是选择的解决方案：

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) 空间，因为问题需要返回数组列表。所以这个空间已经占了。

哪一个是真的？

标签： javaalgorithmdata-structuresbig-ospace-complexity

解决方案

绝对 O(n)

  • 由于List的大小取决于 的大小 ansmatrix，我们可以说这O(1)不是答案。这是因为O(1)表示一个常数空间，这里不是这样。
  • List 的ans确切大小为n = width * height，这将允许它包含 中的所有项目matrix。
  • 如果我们matrix的大小翻倍，那么我们的大小ans也会翻倍，因为项目的数量翻了一番。这表明 和 的大小之间存在线性关系matrixans。那么我们可以说我们的空间确实是复杂的O(n)。

推荐阅读