怎么做查询网站后台,网站慢的原因,定制网站建设的流程,中国建设论坛网站大全哈希表
map set 数组
在C中#xff0c;set 和 map 分别提供以下三种数据结构#xff0c;其底层实现以及优劣如下表所示#xff1a;
集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::set红黑树有序否否O(log n)O(log n)std::multiset红黑树有序是否…哈希表
map set 数组
在C中set 和 map 分别提供以下三种数据结构其底层实现以及优劣如下表所示
集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::set红黑树有序否否O(log n)O(log n)std::multiset红黑树有序是否O(logn)O(logn)std::unordered_set哈希表无序否否O(1)O(1)
std::unordered_set底层实现为哈希表std::set 和std::multiset 的底层实现是红黑树
红黑树是一种平衡二叉搜索树所以key值是有序的但key不可以修改改动key值会导致整棵树的错乱所以只能删除和增加。
映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::map红黑树key有序key不可重复key不可修改O(logn)O(logn)std::multimap红黑树key有序key可重复key不可修改O(log n)O(log n)std::unordered_map哈希表key无序key不可重复key不可修改O(1)O(1)
std::unordered_map 底层实现为哈希表std::map 和std::multimap 的底层实现是红黑树。
同理std::map 和std::multimap 的key也是有序的
Set与Multiset-笔记-CSDN博客
有效的字母异位词
思路
定义一个数组叫做record用来上记录字符串s里字符出现的次数
242. 有效的字母异位词 - 力扣LeetCode
两个数组的交集 class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setintresult_set;unordered_setintnums_set(nums1.begin(),nums1.end());for(auto n2:nums2){if(nums_set.find(n2)!nums_set.end()){result_set.insert(n2);}}return vectorint(result_set.begin(),result_set.end());}
};两数之和
在遍历数组的时候只需要向map去查询是否有和目前遍历元素匹配的数值如果有就找到的匹配对如果没有就把目前遍历的元素放进map中因为map存放的就是我们访问过的元素
class Solution {
public:vectorint twoSum(vectorint nums, int target) {std::unordered_map int,int map;for(int i 0; i nums.size(); i) {// 遍历当前元素并在map中寻找是否有匹配的keyauto iter map.find(target - nums[i]); if(iter ! map.end()) {return {iter-second, i};}// 如果没找到匹配对就把访问过的元素和下标加入到map中map.insert(pairint, int(nums[i], i)); }return {};}
};1. 两数之和 - 力扣LeetCode
四数之和
遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。 再遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来。
三数之和
双指针 依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。
如果nums[i] nums[left] nums[right] 0 说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。
如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止
