两个数组的交集2

两个数组的交集2

350. 两个数组的交集 II - 力扣（LeetCode） (leetcode-cn.com)

思路

用 c++ STL 来做

I want to perform a multi-set intersection using C++ - Stack Overflow

使用 set_intersection 函数

(27条消息) 【C++】关于 std::set_intersection( ) 函数用法_Sim0Hayha的博客-CSDN博客_set_intersection

根据源码自己实现 set_intersection

源码来自

https://blog.csdn.net/Sim0Hayha/article/details/80043558#:~:text=线性复杂度，其-,实现,-为：

STL 数据结构

multiset

int count( const T & val);	统计有多少个元素的值和 val 相等
void insert(iterator first, iterator last);	将区间 [first, last) 中的元素插人容器

vector emplace_ back

C++ STL vector添加元素（push_back()和emplace_back()）详解 (biancheng.net)

代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        multiset<int> s1,s2;
        s1.insert(nums1.begin(), nums1.end());
        s2.insert(nums2.begin(), nums2.end());
        vector<int> result;

        auto i = s1.begin();
        auto j = s2.begin();
    	// 思路来源 https://blog.csdn.net/Sim0Hayha/article/details/80043558
        while (i != s1.end() && j != s2.end())
        {
            if (*i < *j)
                i++;
            else if (*j < *i)
                j++;
            else
            {
                result.emplace_back(*i);
                i++;
                j++;
            }
        }   
        return result; 
    }
};