你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

c++中map的特性

2021-11-20 0:27:37

c++中map的特性


刚刚在力扣做题:
https://leetcode-cn.com/problems/longest-harmonious-subsequence/

wa代码是这样的:

class Solution {
public:
unordered_map<int,int> mp;
    int findLHS(vector<int>& nums) {
        /*
        最大最小差别不超过1
        既我们可以用哈希表统计出所有取值
        然后遍历取值,对于每个取值
        ans取max(cnt[val]*(cnt[val+1]?1:0)+cnt[val+1],ans)即可
        */
    for(auto it:nums)
    mp[it]++;
    
    int ans=0;
    for(auto it:mp){
        ans=max(it.second*(mp[it.first+1]?1:0)+mp[it.first+1],ans);
    }
    return ans;
    }
};

后来才发现是数组中不存在的数字也被统计到了map中去,为什么会这样呢?
经过实验后发现:

#include<iostream>
#include<map>
#include<unordered_map>
using namespace std;

int main(){
	unordered_map<int,int> mp;
	cout<<mp[0]<<" ";
	cout<<mp.size();
	
}

该代码输出为0 1,也就是说,我虽然没有往map里添值,但是我查过值(cout<<mp[0]<<" ";这句),只要查过值,无论该值之前是否存在,都会将该值插入进去,为了避免这种情况,我们需要在插入前判断:

        if(mp.find(it.first+1)!=mp.end())

然后在执行逻辑就好了!

修改过后,AC了:

class Solution {
public:
map<int,int> mp;
    int findLHS(vector<int>& nums) {
        /*
        最大最小差别不超过1
        既我们可以用哈希表统计出所有取值
        然后遍历取值,对于每个取值
        ans取max(cnt[val]*(cnt[val+1]?1:0)+cnt[val+1],ans)即可
        */
    for(auto it:nums)
    mp[it]++;
    
    int ans=0;
    for(auto it:mp){            
        if(mp.find(it.first+1)!=mp.end())
            ans=max(it.second+mp[it.first+1],ans);        
        }
       
    return ans;
    }
};