查找问题

有两类查找问题

1.查找有无   

set 集合

2.查找对应关系（键值对应）

map 字典

通常语言的标准库中都内置set和map

叫容器类

屏蔽了实现细节

了解语言中标准库里常见容器类的使用

常见操作：

inset find erase（删除）change（主要针对map）

349题

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [9,4]

说明:

输出结果中的每个元素一定是唯一的。

我们可以不考虑输出结果的顺序。

题目

class Solution {

public:

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

        set<int> record;

        for(int i=0;i<nums1.size();i++)

        record.insert(nums1[i]);//set中不能承载重复的元素，所以多次inset没有关系

        set<int> resultSet;

        for(int i=0;i<nums2.size();i++)

            if( record.find(nums2[i]) != record.end() )//如果不等于说明存在在record中，接下来只需记录下来，end只是迭代器指针

                resultSet.insert(nums2[i]);

        vector<int> resultVector;//返回的是vector类型

        for(set<int>::iterator iter=resultSet.begin();iter!=resultSet.end();iter++)//迭代器

        resultVector.push_back(*iter);//遍历，塞进去

        return resultVector;

    }

};

题目

350. 两个数组的交集 II

题目

class Solution {

public:

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

        map<int,int> record;

        for(int i=0;i<nums1.size();i++)

            record[nums1[i]]++;

        vector<int> resultVector;

        for(int i=0;i<nums2.size();i++)

            if(record[nums2[i]]>0){

                resultVector.push_back(nums2[i]);//表示出现了塞入；

                record[nums2[i]]--;//频率就减一以便符合上面的条件方便重复元素

            }

        return resultVector;

    }

};

solution

类似问题LeetCode242,202问题290。205.451