做视频的音乐哪里下载网站/网站seo策划
数组的操作
声明
本文大部分内容出自LeetCode官方，掺杂一部分个人学习和理解的笔记，原文出处如下：
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/array-and-string/yjcir/
来源：力扣（LeetCode） 著作权归作者所有。
商业转载请联系作者获得授权，非商业转载请注明出处。
学习目标
对于数组而言，我们需要做到理解的是：
- 数组是如何在内存中存储的？
- 数组的索引是如何建立的？
- 数组的基本操作有哪些？
- 我们该如何理解数组的一些基本操作？
- 自己熟悉的语言里，数组对应的操作的接口都是哪些？
读取元素
读取数组中的元素，是通过访问索引的方式来读取的，索引一般从 0 开始。
在计算机中，内存可以看成一些已经排列好的格子，每个格子对应一个内存地址。一般情况下，数据会分散地存储在不同的格子中。
而对于数组，计算机会在内存中为其申请一段 连续 的空间，并且会记下索引为 0 处的内存地址。以数组 ["C", "O", "D", "E", "R"] 为例，它的各元素对应的索引及内存地址如下图所示。
假如我们想要访问索引为 2 处的元素 "D" 时，计算机会进行以下计算：
- 找到该数组的索引
0的内存地址：2008； - 将内存地址加上索引值，作为目标元素的地址，即
2008 + 2 = 2010，对应的元素为"D"，这时便找到了目标元素。
我们知道，计算内存地址这个过程是很快的，而我们一旦知道了内存地址就可以立即访问到该元素，因此它的时间复杂度是常数级别，为
查找元素
假如我们对数组中包含哪些元素并不了解，只是想知道其中是否含有元素 "E"，数组会如何查找元素 "E" 呢？
与读取元素类似，由于我们只保存了索引为 0 处的内存地址，因此在查找元素时，只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素，则停止查找；否则继续搜索直到到达数组的末尾。
我们发现，最坏情况下，搜索的元素为 "R" ，或者数组中不包含目标元素时，我们需要查找 n次，n 为数组的长度，因此查找元素的时间复杂度为
插入元素
假如我们想在原有的数组中再插入一个元素 "S" 呢？
如果要将该元素插入到数组的末尾，只需要一步。即计算机通过数组的长度和位置计算出即将插入元素的内存地址，然后将该元素插入到指定位置即可。
然而，如果要将该元素插入到数组中的其他位置，则会有所区别，这时我们首先需要为该元素所要插入的位置腾出空间，然后进行插入操作。比如，我们想要在索引 2 处插入 "S"。
我们发现，如果需要频繁地对数组元素进行插入操作，会造成时间的浪费。事实上，另一种数据结构，即链表可以有效解决这个问题，我们将在另外的[链表]章节中进行学习。
删除元素
删除元素与插入元素的操作类似，当我们删除掉数组中某个元素后， 数组会留下 空缺 的位置， 二数组中的元素在内存中是连续的，这就使得后面的元素需要对该位置进行 填补 操作。
以删除索引 1 中的元素 "O" 为例，具体过程如图所示。
当数组的长度为$n$时， 最坏情况下，我们删除第一个元素，共需要的步骤数为
1 作为删除操作， 小结
我们现在来回答之前自己给自己提出的几个问题：
- 数组是如何在内存中存储的？ 答案： 我的理解中，数组在内存中是一段连续的地址，每个元素根据索引进行内存地址的偏移。
- 数组的索引是如何建立的？ 答案： 我的理解中，通过内存地址的0号地址标记加上内存地址数据偏移量能够建立数组的索引地址。
- 数组的基本操作有哪些？ 答案： 就如同本次学习提到的，基本的增删查改的操作，然后，在有些语言里面还能有一些迭代器对数组可以进行操作。
- 我们该如何理解数组的一些基本操作？ 答案： 数组的操作其实就是对一段连续内存地址中的数据进行偏移后，对某种同一个类型的数据进行处理的过程，操作过程需要移动一些元素。
- 自己熟悉的语言里，数组对应的操作的接口都是哪些？ 答案： 我自己熟悉的C++里面的std::vector的相关接口有
- 增加：push_back()接口。
- 查： at(), []操作符都可以进行操作。
- 插入元素：insert()接口。
- 删除元素： clear() 删除所有， pop_back()删除最后一个， erase删除某个特定区间段的元素。
c++ vector使用的一些例子
例子主要来源于 - cpp reference
基础创建
#include <iostream>
#include <vector>int main()
{// Create a vector containing integersstd::vector<int> v = {7, 5, 16, 8};// Add two more integers to vectorv.push_back(25);v.push_back(13);// Iterate and print values of vectorfor(int n : v) {std::cout << n << 'n';}
}
一些接口的调用
clear()
#include <algorithm>
#include <iostream>
#include <vector>int main()
{std::vector<int> container{1, 2, 3};auto print = [](const int& n) { std::cout << " " << n; };std::cout << "Before clear:";std::for_each(container.begin(), container.end(), print);std::cout << "nSize=" << container.size() << 'n';std::cout << "Clearn";container.clear();std::cout << "After clear:";std::for_each(container.begin(), container.end(), print);std::cout << "nSize=" << container.size() << 'n';
}
// out put:
// Before clear: 1 2 3
// Size=3
// Clear
// After clear:
// Size=0
insert
#include <iostream>
#include <vector>void print_vec(const std::vector<int>& vec)
{for (auto x: vec) {std::cout << ' ' << x;}std::cout << 'n';
}int main ()
{std::vector<int> vec(3,100);print_vec(vec);auto it = vec.begin();it = vec.insert(it, 200);print_vec(vec);vec.insert(it,2,300);print_vec(vec);// "it" no longer valid, get a new one:it = vec.begin();std::vector<int> vec2(2,400);vec.insert(it+2, vec2.begin(), vec2.end());print_vec(vec);int arr[] = { 501,502,503 };vec.insert(vec.begin(), arr, arr+3);print_vec(vec);
}
// output:
100 100 100
200 100 100 100
300 300 200 100 100 100
300 300 400 400 200 100 100 100
501 502 503 300 300 400 400 200 100 100 100
erase
#include <vector>
#include <iostream>void print_container(const std::vector<int>& c)
{for (auto &i : c) {std::cout << i << " ";}std::cout << 'n';
}int main( )
{std::vector<int> c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};print_container(c);c.erase(c.begin());print_container(c);c.erase(c.begin()+2, c.begin()+5);print_container(c);// Erase all even numbers (C++11 and later)for (auto it = c.begin(); it != c.end(); ) {if (*it % 2 == 0) {it = c.erase(it);} else {++it;}}print_container(c);
}
// output
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 6 7 8 9
1 7 9
push_back
#include <vector>
#include <iostream>
#include <iomanip>int main()
{std::vector<std::string> letters;letters.push_back("abc");std::string s = "def";letters.push_back(std::move(s));std::cout << "vector holds: ";for (auto&& i : letters) std::cout << std::quoted(i) << ' ';std::cout << "nMoved-from string holds " << std::quoted(s) << 'n';
}
// output
vector holds: "abc" "def"
Moved-from string holds ""
成长，就是一个不动声色的过程，一个人熬过一些苦，才能无所不能。