算法初学者的第一个数据结构，数组和vector

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们正式进入了《代码随想录》的第三章，前面写了一些关于时间复杂度、空间复杂度以及算法优化思路的内容。这些内容很容易被忽略，但是又很重要，因此稍微多花了点篇幅。从第三章开始就要正式进入算法、数据结构的内容了。

区分算法和数据结构

我在学习算法以及和大家讨论的过程当中发现了一个很有意思的现象，很多人虽然知道算法和数据结构并不是同一个范畴，但是往往在理解的时候会把它们当做同一个东西来理解。尤其是在学习的时候，都会倾向性地把算法和数据结构混为一谈。

这里稍微简单提一下这两者的一个区别，数据结构更像是基础，它主要负责数据的存储以及查询。算法更多是应用在数据结构之上的方法，用来实现某种功能或者达成某种目的。

比如说排序问题，我们需要读入一批数据返回排序之后的结果。数据读入之后通常会放入数组当中，数组就是一个数据结构。而排序算法，则是应用在数组之上的方法，用来对数组当中的元素进行排序。再比如图论当中，有好几种数据结构都可以用来存储图。不管我们使用哪一种，在我们需要求具体数值的时候，都可以在上面再套用某个算法来实现。

之所以提这个问题，是希望帮助大家树立正确的认知。这样在解决具体算法问题的时候，我们就可以清晰地知道当下我们需要使用什么样的数据结构，在这样的数据结构之上我们又需要应用哪些算法。将问题这样一分为二思考之后，很多时候可以大大简化我们思维的复杂度，帮助我们更好地理清算法逻辑。

数组

数组是算法当中我们最常用的数据结构，几乎没有之一。

实际上在正规的数据结构书籍当中，一般不会单独将数组作为一个数据结构进行介绍。取而代之的是线性表，线性表表明存储结构是线性的。而数组其实是线性表的一种具体实现，除了数组之外，还有很多其他结构可以线性存储数据，比如vector、链表等等。

这里只是简单提一下，不做过多延伸。

在C++当中，数组的长度是连续并且固定的，在我们声明数组之后，数组的长度就不会再变化。在刷题的时候，如果要使用数组，最好一次性就给与足够的空间。

C++中有一个和数组非常近似的STL，叫做vector。vector基于数组实现，支持末尾插入新元素，并且支持元素的删除。其中元素的删除是

的操作，插入操作也不是完全

的。感兴趣的同学可以读一下vector或者STL的源码，C++的STL代码都是大神写的，非常值得一读。

另外，值得一提的是，在C++当中，数组本质上也是一种指针，是指向数组中第0个元素。

double balance[5] = {1000.0, 2.0, 3.4, 17.0, 50.0};  

本质上balance是一个指向&balance[0]的指针，不过是常量指针，不能被赋值。但我们可以把它赋给指针：

double *p = balance;

并且我们也可以使用指针的取值符号来获取数组中的元素：

cout << *(balance + 1) << endl;

等同于：

cout << balance[1] << endl;

二维或者高维数组也类似，只不过情况会复杂一些。因为篇幅以及使用频率不高的原因，这里就不过多赘述了。大家心里清楚数组本质上就是指针即可。

和链表相比，数组的优势在于极快的元素访问速度以及明确的长度，我们可以在

的时间内访问数组中的任意一个元素。而链表则不行，需要

。另外数组实现简单，几乎可以说是上手可用，而链表的实现和debug非常复杂。

在C++当中，很多大佬喜欢使用vector代替数组。除了支持末尾插入、弹出元素之外，vector还拥有丰富的api。这里简单列举几个。

插入、删除

vector<int> vec;
auto it = vec.begin(); // 迭代器
vec.insert(it, 10); // 插入在it之前
vec.erase(it);
vec.erase(it, it+4); // 批量删除
vec.push_back(10); // 末尾插入
auto x = vec.pop_back(); // 末尾弹出

访问

vec.front(); // 第一个元素
vec.back(); // 最后一个元素
vec[i]; // 访问第i个元素

排序

sort(vec.begin(), vec.end()); // 默认从小到大排
sort(vec.begin(), vec.end(), greater<int>()); // 从到大小排

二分

sort(vec.begin(), vec.end());
auto it = lower_bound(vec.begin(), vec.end(), 10); // 返回大于等于10的第一个位置
auto it = upper_bound(vec.begin(), vec.end(), 10); // 返回大于等于10的最后一个位置

STL可以说是C++搞算法竞赛的精髓，搞熟悉了对于编码事半功倍，非常有帮助。因此非常建议大家花点时间学习熟悉一下C++中STL的用法，基本上每次LeetCode周赛都能用得上。

关于数组的基本知识就介绍这么多，下一篇我们将会迎来基于数组的第一个算法，也是最经典的算法——二分。