建设部网站举报,php网站设计流程,ui培训班学费价格,wordpress支持手机适应文章目录 C STL库之Vector简介及例题#xff08;哈希表#xff09;#xff08;一#xff09;一、初始化二、数值操作例题题解哈希表简析C哈希表初始化C哈希表基本操作 C STL库之Vector简介及例题#xff08;哈希表#xff09;#xff08;一#xff09;
Vector是一个能… 文章目录 C STL库之Vector简介及例题哈希表一一、初始化二、数值操作例题题解哈希表简析C哈希表初始化C哈希表基本操作 C STL库之Vector简介及例题哈希表一
Vector是一个能够存放任意类型的动态数组能够增加和压缩数据。
特性1顺序容器中的元素按照严格的线性顺序排列可以通过元素的下标访问对应的元素。
特性2支持对序列中的任意元素进行快速直接查询可以在序列末尾相对快速地添加/删除元素的操作所以不知道自己所需的数组大小时可以用Vector以节约空间。
注意 Vector容器的用法有很多内置算法函数也有很多这里就不一一介绍了就写一些常用的好理解的如果后面遇到了我会在文章里具体解释。
一、初始化
使用vector容器时需要声明头文件#inlcude vector;
vector容器可以是多种数据形式例如int / char / string / 自定义类型 / 结构体类型等等
具体初始化方法如下代码及解释所示
#include vector // 头文件 #include vector;
#include iostream
using namespace std;int main() {// 限制整形数组长度为10默认值为0vectorint vec_int_limit(10);// 不限制数组长度vectorint vec_int;// 直接给数组赋值vectorint vec_int_nums{ 1,2,3,4,5,6 };// 建立string类型数组长度为10每个默认为uhaovectorstring string_array(10, uhao);// 建立二维数组可直接赋值vectorvectorint two_array{ {1,2,3},{4,5,6} };// 从原数组中取一段值赋值,goal_array数组结果是{654}// 如下代码区间为[ original_array.begin() , original.begin()3 )vectorint original_array{ 6,5,4,3,2,1 };vectorint goal_array(original_array.begin(),original_array.begin() 3);return 0;
}二、数值操作
Vector容器有很多种函数可以对内容进行不同操作这里就介绍一些常用的后续用到别的会再解释。
创建一个数组并直接赋值vectorint vec{ 7,5,3,1,2,0 };
访问数组下标中的元素vec[1]; // 二维数组同理vec[num1][num2]
获取数组下标中的元素同 vec[1]vec.at(1);
在尾部添加一个元素 8vec.push_back(8);
删除最后一个元素vec.pop_back();
获取vector数组元素个数即长度vec.size();
获取数组第一个元素的指针vec.begin();
获取数组最后一个元素1的指针vec.end();
获取数组第一个元素值vec.front();
获取数组最后一个元素值vec.back();
与数组other_array交换数据(可以说是用other_array替换vec)vec.swap(other_array);
判断是否为空为空返回1不为空返回0vec.empty();
在第i1个元素前插入数据evec.insert(vec.begin() i , e);
在倒数第i个元素前面插入evec.insert(vec.end() - i , e); 例题
力扣经典第1题《两数之和》
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那两个整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 题解
思路 1
用两个for循环暴力破解这个方法比较简单就不写解析了代码如下
vectorint twoSum(vectorint nums, int target) {int n nums.size();for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums[i] nums[j] target) {return {i, j};}}}return {};}// 来源力扣LeetCode思路 2
用两个for循环的时间复杂度比较高所以如果我们如果能够先确定一个数字然后在数组余下的数字中迅速找出target-x那么我们的效率肯定会翻倍
所以我们这个时候就会想到**哈希表。**
哈希表简析
哈希表是一种数据结构它可以提供非常快速的数据插入和查找操作。它通过一个叫做哈希函数的过程将存储的数据项与一个特定的索引关联起来这个索引指示了数据项在表中的位置。
C哈希表初始化
#include iostream
#include unordered_map // 哈希表头文件
using namespace std;int main()
{unordered_mapint, int hashMap; // 创建哈希表// 进行赋值hashMap[1] 10; hashMap[2] 20;hashMap[3] 30;// it-first 用于获取当前迭代器it指向的元素下标// it-second 用于获取当前迭代器it指向的元素值for (auto it hashMap.begin(); it ! hashMap.end(); it) {cout key: it-first value: it-second endl;}/*输出结果为key:1 value:10key:2 value:20key:3 value:30*/return 0;
}C哈希表基本操作
1. 插入操作
// 使用下标操作符插入元素
hashMap[key] value;// 使用insert()方法插入元素
hashMap.insert({key, value});2. 删除操作
hashMap.erase(key); // 删除指定元素key3. 访问
hashMap[key]; // 直接访问 或用迭代器见上哈希表简析代码★4. 判断元素是否存在
// 方法1 根据哈希表的特性如果一个元素被注册过也就是存在则count值为1否则为0
if(hashMap.count(key) 0){// 存在
}
else{// 不存在
}// 方法2 使用find函数如果查找的key不存在于哈希表则返回值与hashMap.end()相等反之同理
if (hashMap.find(key) ! hashMap.end()) {cout 存在;
}
else {cout 不存在;
} 大致了解了哈希表的应用之后我们可以得出以下优化后的代码
vectorint twoSum(vectorint nums, int target) {unordered_mapint, int m;for (int i 0; i nums.size(); i) {if (m.count(target - nums[i])) {return {m[target - nums[i]], i};}m[nums[i]] i;}return {};}代码解析
1. 创建一个空的哈希表 unordered_mapint, int m; 用来存储数组值到索引的映射。 2. 使用一个for循环遍历整个输入数组 nums。 3. 在循环内部使用 if 语句检查哈希表中是否存在一个键值对其键target - nums[i]是目标值与当前元素值的差。 4. 如果这样的键存在说明我们找到了两个数它们的和等于目标值target - nums[i] 是之前某个元素的值nums[i] 是当前元素的值。这时我们返回一个包含两个下标的数组先前元素的下标 m[target - nums[i]] 和当前元素的下标 i。 5. 如果没有找到则将当前元素的值和它的下标 i 加入到哈希表中即 m[nums[i]] i; 6. 如果整个数组都遍历完了还没有找到这样的两个数则函数返回一个空数组 return {};。 基本上这段代码利用哈希表存储已经遍历过的元素的值和对应的下标借助这个表我们能在O(1)的时间复杂度内查找到 target - nums[i]。因此整个函数的时间复杂度是O(n)其中n是数组 nums 的长度。这是一个高效的解决方案因为它避免了使用两个嵌套循环这在最坏的情况下会导致O(n^2)的时间复杂度。
