当前位置：首页 > article >正文

《征服数据结构》滚动数组

article 2024/9/23 11:18:21

摘要：

1，一维滚动数组的介绍

2，多维滚动数组的介绍

1，一维滚动数组的介绍

滚动数组不是一种数据结构，它是一种算法优化思想，滚动数组的作用在于优化空间，降低空间复杂度，每次使用固定的一些存储空间。

比如我们常见的斐波那契数列：f[n] = f[n – 1] + f[n – 2] ，普通的写法如下：

Java 代码：

// 1、2、3、5、8、13、21、34、……
private int fibonacci(int n) {// n > 0
    if (n == 1 || n == 2)
        return n;
    int[] res = new int[n + 1];
    res[0] = 1;
    res[1] = 2;
    for (int i = 2; i <= n; i++)
        res[i] = res[i - 1] + res[i - 2];
    return res[n];
}

C++ 代码：

public:
    // 1、2、3、5、8、13、21、34、……
    int fibonacci(int n) {// n > 0
        if (n == 1 || n == 2)
            return n;
        vector<int> res(n + 1);
        res[0] = 1;
        res[1] = 2;
        for (int i = 2; i <= n; i++)
            res[i] = res[i - 1] + res[i - 2];
        return res[n];
    }

如下图所示，虽然定义一个很长的数组，但每次都用最近的 3 个，前面的都浪费了，所以我们可以使用滚动数组，只需要一个长度为 3 的数组即可。