飞虎队队长 發表於 2025-12-15 08:35:21

C++ set和multiset的使用小结

<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>1. 序列式容器和关联式容器(了解)</li><li>2. set系列的使用</li><ul class="second_class_ul"><li>2.1 set类的介绍</li><li>2.2 set的构造和迭代器</li><ul class="third_class_ul"><li>0.构造:</li><li>1. 空构造(empty (1))</li><li>2. 范围构造(range (2))</li><li>3. 拷贝构造(copy (3))</li><li>4. 初始化列表(C++11)</li></ul><li>2.3 修改器(Modifiers)的成员函数</li><ul class="third_class_ul"><li>0. 迭代器</li><li>1. insert:插入元素</li><li>2. erase:删除元素</li><li>3. swap:交换两个set的内容(与算法库swap对比)</li><li>4. clear:清空所有元素</li><li>5. emplace:构造并插入元素(C++11+)</li><li>6. emplace_hint:带位置提示的构造插入(C++11+)</li></ul><li>2.4 find(与算法库find的对比)</li><ul class="third_class_ul"></ul><li>2.5 key_comp &amp;&amp; value_comp</li><ul class="third_class_ul"><li>代码示例</li></ul><li>2.6 count(与find比较)</li><ul class="third_class_ul"><li>与find的区别</li></ul><li>2.7 lower_bound &amp;&amp; upper_bound</li><ul class="third_class_ul"></ul></ul><li>3. multiset</li><ul class="second_class_ul"><li>3.1 核心特性差异</li><ul class="third_class_ul"></ul><li>3.2 接口行为差异</li><ul class="third_class_ul"></ul><li>3.3 使用场景差异</li><ul class="third_class_ul"></ul></ul><li>4. 例题部分</li><ul class="second_class_ul"><li>4.1 环形链表 II</li><ul class="third_class_ul"></ul><li>4.2 两个数组的交集</li><ul class="third_class_ul"></ul></ul></ul></div><p class="maodian"></p><h2>1. 序列式容器和关联式容器(了解)</h2>
<p>前面我们已经接触过STL中的部分容器如:<code>string、vector、list、deque、array、forward_list等</code>,这些容器统称为序列式容器,因为逻辑结构为线性序列的数据结构,两个位置存储的值之间一般没有紧密的关联关系,比如交换一下,他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。</p>
<p>关联式容器也是用来存储数据的,与序列式容器不同的是,关联式容器逻辑结构通常是非线性结构,两个位置有紧密的关联关系,交换一下,他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有<code>map/set</code>系列和<code>unordered_map/unordered_set</code>系列。</p>
<p><code>map</code>和<code>set</code>底层是红黑树,红黑树是一颗平衡二叉搜索树。<code>set</code>是<code>key</code>搜索场景的结构,<code>map</code>是<code>key/value</code>搜索场景的结构。<br />说人话 就是<code>map set</code>的值不能改 改了结构会被破坏。</p>
<p class="maodian"></p><h2>2. set系列的使用</h2>
<p class="maodian"></p><h3>2.1 set类的介绍</h3>
<ul><li><code>set</code>的声明如下,<code>T</code>就是set底层关键字的类型</li><li><code>set</code>默认要求<code>T</code>支持小于比较,如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数。</li><li><code>set</code>底层存储数据的内存是从空间配置器申请的,如果需要可以自己实现内存池,传给第三个参数。</li><li>一般情况下,我们都不需要传后两个模版参数。</li><li><code>set</code>底层是用红黑树实现,增删查效率是<span><span><span> O ( l o g N ) O(logN) </span><span><span><span>O</span><span>(</span><span>l</span><span>o</span><span>g</span><span>N</span><span>)</span></span></span></span></span>,迭代器遍历是走的搜索树的中序,所以是有序的。</li><li>与<code>vector/list</code>等容器的使用,STL容器接口设计,高度相似,所以这里我们就不再一个接口一个接口的介绍,挑比较重要的接口进行介绍。</li></ul>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340882.png" /></p>
<p class="maodian"></p><h3>2.2 set的构造和迭代器</h3>
<p class="maodian"></p><h4>0.构造:</h4>
<p><code>set</code> 的支持正向和反向迭代遍历,遍历默认按升序顺序,因为底层是二叉搜索树,迭代器遍历走的中序;支持迭代器就意味着支持范围 for,<code>set</code> 的 <code>iterator</code> 和 <code>const_iterator</code> <strong>都不支持迭代器修改数据</strong>,修改关键字数据,防止破坏底层搜索树的结构。</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340899.png" /></p>
<p class="maodian"></p><h4>1. 空构造(empty (1))</h4>
<div class="jb51code"><pre class="brush:cpp;">explicit set (const key_compare&amp; comp = key_compare(),
               const allocator_type&amp; alloc = allocator_type());
</pre></div>
<ul><li><strong>作用</strong>:创建空的<code>set</code>容器。</li><li><strong>参数</strong>:<ul><li><code>comp</code>:可选,自定义的键比较规则(默认使用<code>key_compare</code>,即<code>&lt;</code>比较);</li><li><code>alloc</code>:可选,内存分配器(默认使用<code>allocator_type</code>)。</li></ul></li></ul>
<p class="maodian"></p><h4>2. 范围构造(range (2))</h4>
<div class="jb51code"><pre class="brush:cpp;">template &lt;class InputIterator&gt;
set (InputIterator first, InputIterator last,
   const key_compare&amp; comp = key_compare(),
   const allocator_type&amp; alloc = allocator_type());
</pre></div>
<ul><li><strong>作用</strong>:将迭代器<code>[first, last)</code>范围内的元素插入<code>set</code>(自动<strong>去重</strong>并按规则排序)。</li><li><strong>参数</strong>:<ul><li><code>first/last</code>:输入迭代器,指定待插入元素的范围;</li><li><code>comp/alloc</code>:同空构造的可选参数。</li></ul></li></ul>
<p class="maodian"></p><h4>3. 拷贝构造(copy (3))</h4>
<div class="jb51code"><pre class="brush:cpp;">set (const set&amp; x);
</pre></div>
<ul><li><strong>作用</strong>:创建一个与已有<code>set</code>对象<code>x</code>内容完全相同的新<code>set</code>。</li></ul>
<p class="maodian"></p><h4>4. 初始化列表(C++11)</h4>
<div class="jb51code"><pre class="brush:cpp;">void test_set1()
{
    set&lt;int&gt; s = { 5,1,5,3,4,2,6,83,9,10,22 };
    // 中序,排序+去重
    set&lt;int&gt;::iterator it = s.begin();
    while (it != s.end())
    {
      // 普通迭代器也不支持修改
      // *it = 1;
      
      cout &lt;&lt; *it &lt;&lt; " ";
      ++it;
    }
    cout &lt;&lt; endl;
}
</pre></div>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340851.png" /></p>
<p class="maodian"></p><h3>2.3 修改器(Modifiers)的成员函数</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340813.jpg" /><br />这是C++ <code>std::set</code>的<strong>修改器(Modifiers)成员函数</strong>,负责对<code>set</code>的元素进行增删等操作。以下结合代码示例逐一讲解:</p>
<p class="maodian"></p><h4>0. 迭代器</h4>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340815.jpg" /></p>
<p>这个太基础了 我个人感觉实在没什么可以说的 唯一要注意的就是 不能通过迭代器修改里面的值。</p>
<p class="maodian"></p><h4>1. insert:插入元素</h4>
<p><strong>功能</strong>:向<code>set</code>中插入键值(自动去重、按规则排序)。<br /><strong>代码示例</strong>:</p>
<div class="jb51code"><pre class="brush:cpp;">#include &lt;set&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
    set&lt;int&gt; s;
    // 插入单个元素
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2); // 重复元素,插入失败(set自动去重)

    // 遍历输出:1 2 3(默认升序)
    for (int val : s) cout &lt;&lt; val &lt;&lt; " ";
    return 0;
}
</pre></div>
<p class="maodian"></p><h4>2. erase:删除元素</h4>
<p><strong>功能</strong>:删除<code>set</code>中的元素(支持按键值、迭代器、范围删除)。<br /><strong>代码示例</strong>:</p>
<div class="jb51code"><pre class="brush:cpp;">int main() {
    set&lt;int&gt; s = {1,2,3,4,5};
    // 1. 按键值删除
    s.erase(3);
    // 2. 按迭代器删除
    auto it = s.find(4);
    if (it != s.end()) s.erase(it);
    // 3. 按范围删除(删除[begin, end))
    s.erase(s.begin(), s.end()); //左闭右开

    cout &lt;&lt; s.size(); // 输出0
    return 0;
}
</pre></div>
<p class="maodian"></p><h4>3. swap:交换两个set的内容(与算法库swap对比)</h4>
<p><strong>功能</strong>:交换当前<code>set</code>与另一个<code>set</code>的所有元素(底层仅交换内部指针,效率高,而<strong>算法库</strong>中<code>swap</code>则涉及深层拷贝等)。<br /><strong>代码示例</strong>:</p>
<div class="jb51code"><pre class="brush:cpp;">int main() {
    set&lt;int&gt; s1 = {1,2,3};
    set&lt;int&gt; s2 = {4,5,6};
    s1.swap(s2);

    // s1变为{4,5,6},s2变为{1,2,3}
    for (int val : s1) cout &lt;&lt; val &lt;&lt; " "; // 输出4 5 6
    return 0;
}
</pre></div>
<p class="maodian"></p><h4>4. clear:清空所有元素</h4>
<p><strong>功能</strong>:删除<code>set</code>中的所有元素,使其变为空容器。<br /><strong>代码示例</strong>:</p>
<div class="jb51code"><pre class="brush:cpp;">int main() {
    set&lt;int&gt; s = {1,2,3};
    s.clear();
    cout &lt;&lt; s.empty(); // 输出1(表示容器为空)
    return 0;
}
</pre></div>
<p class="maodian"></p><h4>5. emplace:构造并插入元素(C++11+)</h4>
<p><strong>功能</strong>:直接在<code>set</code>中构造元素(避免临时对象拷贝,比<code>insert</code>更高效)。<br /><strong>代码示例</strong>:</p>
<div class="jb51code"><pre class="brush:cpp;">int main() {
    set&lt;pair&lt;int, string&gt;&gt; s;
    // emplace直接构造pair(无需手动创建临时pair)
    s.emplace(1, "apple");
    // 等价于insert,但emplace更高效
    s.insert(pair&lt;int, string&gt;(2, "banana"));

    return 0;
}
</pre></div>
<p class="maodian"></p><h4>6. emplace_hint:带位置提示的构造插入(C++11+)</h4>
<p><strong>功能</strong>:在指定迭代器位置附近构造并插入元素(若位置合理,可提升插入效率)。<br /><strong>代码示例</strong>:</p>
<div class="jb51code"><pre class="brush:cpp;">int main() {
    set&lt;int&gt; s = {1,3,5};
    // 提示在3的位置附近插入2(实际插入到1和3之间)
    auto it = s.find(3);
    s.emplace_hint(it, 2);

    for (int val : s) cout &lt;&lt; val &lt;&lt; " "; // 输出1 2 3 5
    return 0;
}
</pre></div>
<p class="maodian"></p><h3>2.4 find(与算法库find的对比)</h3>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340821.jpg" /></p>
<p>这是C++标准库中<code>std::set::find</code>成员函数的声明(支持C++98及以上版本),其核心信息与使用说明如下:</p>
<div class="jb51code"><pre class="brush:cpp;">iterator find (const value_type&amp; val) const;
</pre></div>
<ul><li><strong>返回值</strong>:<code>iterator</code>(<code>set</code>的迭代器),指向找到的键值<code>val</code>;若<code>val</code>不存在,返回<code>set::end()</code>(尾后迭代器)。</li><li><strong>参数</strong>:<code>const value_type&amp; val</code>,待查找的键值(<code>value_type</code>即<code>set</code>的关键字类型)。</li><li><strong>特性</strong>:<code>const</code>修饰表示该函数不会修改<code>set</code>本身。</li></ul>
<p><code>find</code>是<code>set</code>的<strong>查找接口</strong>,基于底层红黑树的特性,能以<span><span><span> O ( log ⁡ N ) O(\log N) </span><span><span><span>O</span><span>(</span><span>lo<span>g</span></span><span>N</span><span>)</span></span></span></span></span>的时间复杂度快速定位键值,常用于判断元素是否存在、获取元素迭代器。</p>
<ul><li>效率:由于<code>set</code>底层是有序的红黑树,<code>find</code>通过二分查找逻辑实现,效率远高于算法库的<code>find</code>(<span><span><span> O ( N ) O(N) </span><span><span><span>O</span><span>(</span><span>N</span><span>)</span></span></span></span></span>)。</li><li>迭代器特性:<code>set</code>的迭代器是双向迭代器,且不可修改(因为修改键值会破坏<code>set</code>的有序性)。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#include &lt;set&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
    set&lt;int&gt; s = {1, 2, 3, 4, 5};
   
    // 查找键值3
    auto it = s.find(3);
    if (it != s.end()) {
      cout &lt;&lt; "找到元素:" &lt;&lt; *it &lt;&lt; endl; // 输出“找到元素:3”
    }

    // 查找不存在的键值6
    it = s.find(6);
    if (it == s.end()) {
      cout &lt;&lt; "未找到元素" &lt;&lt; endl; // 输出“未找到元素”
    }

    return 0;
}
</pre></div>
<p class="maodian"></p><h3>2.5 key_comp &amp;&amp; value_comp</h3>
<table><thead><tr><th>函数名</th><th>功能描述</th></tr></thead><tbody><tr><td>key_comp</td><td>返回set用于比较**键(key)**的函数对象,是set模板参数中指定的比较类型(默认是less&lt;key_type&gt;)。</td></tr><tr><td>value_comp</td><td>功能与key_comp一致(因为set的键和值是同一类型),返回的比较对象逻辑等同于key_comp。</td></tr></tbody></table>
<blockquote><p>set的底层红黑树依赖比较规则维持有序性,这两个函数可以获取当前set使用的比较逻辑,常用于:</p>
<ol><li>自定义比较规则时,验证或复用set的排序逻辑;</li><li>对set的元素进行外部排序(保持与set内部一致的规则)。</li></ol></blockquote>
<p class="maodian"></p><h4>代码示例</h4>
<div class="jb51code"><pre class="brush:cpp;">#include &lt;set&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
    // 定义一个按降序排序的set
    set&lt;int, greater&lt;int&gt;&gt; s = {3, 1, 2};

    // 获取key_comp比较对象
    auto comp = s.key_comp();

    // 使用comp判断两个键的大小关系(符合set的降序规则)
    bool res = comp(1, 2); // 等价于greater&lt;int&gt;()(1,2),结果为false
    cout &lt;&lt; "1 &gt; 2 ? " &lt;&lt; boolalpha &lt;&lt; res &lt;&lt; endl; // 输出“1 &gt; 2 ? false”

    return 0;
}
</pre></div>
<p class="maodian"></p><h3>2.6 count(与find比较)</h3>
<ul><li><strong>声明</strong>:<code>size_type count (const value_type&amp; val) const;</code></li><li><strong>功能</strong>:统计<code>set</code>中值为<code>val</code>的元素个数(由于<code>set</code>不允许重复元素,返回值只能是<code>0</code>或<code>1</code>)。</li><li><strong>参数</strong>:<code>const value_type&amp; val</code>,待统计的目标值;</li><li><strong>返回值</strong>:<code>size_type</code>(无符号整数类型),表示<code>val</code>在<code>set</code>中的出现次数。</li></ul>
<p>由于<code>set</code>的&ldquo;唯一性&rdquo;特性,<code>count</code>的实际作用是<strong>判断元素是否存在</strong>(返回<code>1</code>表示存在,<code>0</code>表示不存在),效果等价于<code>find(val) != end()</code>,但语义更偏向&ldquo;计数&rdquo;。</p>
<div class="jb51code"><pre class="brush:cpp;">#include &lt;set&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
    set&lt;int&gt; s = {1, 2, 3, 4};

    // 统计存在的元素
    size_t cnt1 = s.count(3);
    cout &lt;&lt; "元素3的出现次数:" &lt;&lt; cnt1 &lt;&lt; endl; // 输出1

    // 统计不存在的元素
    size_t cnt2 = s.count(5);
    cout &lt;&lt; "元素5的出现次数:" &lt;&lt; cnt2 &lt;&lt; endl; // 输出0

    return 0;
}
</pre></div>
<p class="maodian"></p><h4>与find的区别</h4>
<table><thead><tr><th>函数</th><th>功能</th><th>返回值类型</th><th>适用场景</th></tr></thead><tbody><tr><td>find</td><td>查找元素并返回迭代器</td><td>迭代器</td><td>需要获取元素的位置时</td></tr><tr><td>count</td><td>统计元素出现次数</td><td>无符号整数</td><td>仅需判断元素是否存在时</td></tr></tbody></table>
<p>综合对比 在判断元素是否存在时 count 更加方便!</p>
<p class="maodian"></p><h3>2.7 lower_bound &amp;&amp; upper_bound</h3>
<table><thead><tr><th>函数名</th><th>功能描述</th></tr></thead><tbody><tr><td>lower_bound</td><td>返回指向**第一个不小于(&ge;)目标值val**的元素的迭代器;若所有元素都小于val,返回end()。</td></tr><tr><td>upper_bound</td><td>返回指向**第一个大于(&gt;)目标值val**的元素的迭代器;若所有元素都不大于val,返回end()。</td></tr></tbody></table>
<blockquote><p>由于set是有序容器(默认升序),这两个函数通过二分查找(时间复杂度 O ( log ⁡ N ) O(\log N) O(logN))快速定位边界,常用于获取&ldquo;等于val的元素区间&rdquo;([lower_bound, upper_bound))。</p></blockquote>
<div class="jb51code"><pre class="brush:cpp;">#include &lt;set&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
    set&lt;int&gt; s = {1, 3, 5, 7, 9};
    int val = 5;

    // 获取lower_bound:第一个≥5的元素(即5)
    auto lb = s.lower_bound(val);
    cout &lt;&lt; "lower_bound(" &lt;&lt; val &lt;&lt; "): " &lt;&lt; *lb &lt;&lt; endl; // 输出5

    // 获取upper_bound:第一个&gt;5的元素(即7)
    auto ub = s.upper_bound(val);
    cout &lt;&lt; "upper_bound(" &lt;&lt; val &lt;&lt; "): " &lt;&lt; *ub &lt;&lt; endl; // 输出7

    // 若val不存在(如val=4)
    val = 4;
    lb = s.lower_bound(val); // 第一个≥4的元素是5
    ub = s.upper_bound(val); // 第一个&gt;4的元素是5
    cout &lt;&lt; "val=4时,[lb, ub)区间长度:" &lt;&lt; distance(lb, ub) &lt;&lt; endl; // 输出0(无元素)

    return 0;
}
</pre></div>
<p>用处: 删除或者遍历 某一区间的值:</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340822.png" /></p>
<p class="maodian"></p><h2>3. multiset</h2>
<p><code>multiset</code>和<code>set</code>,核心差异集中在<strong>元素唯一性、接口行为、使用场景</strong>三个维度,但是<code>multiset</code>不用单独包含头文件,二者基本完全类似。</p>
<p class="maodian"></p><h3>3.1 核心特性差异</h3>
<table><thead><tr><th>维度</th><th>set</th><th>multiset</th></tr></thead><tbody><tr><td>元素唯一性</td><td>不允许重复元素(键唯一)</td><td>允许重复元素(键可重复)</td></tr><tr><td>底层实现</td><td>红黑树(平衡二叉搜索树)</td><td>红黑树(平衡二叉搜索树)</td></tr><tr><td>有序性</td><td>元素按键有序排列</td><td>元素按键有序排列</td></tr></tbody></table>
<p class="maodian"></p><h3>3.2 接口行为差异</h3>
<p>以常用成员函数为例,两者行为因&ldquo;唯一性&rdquo;产生区别:</p>
<table><thead><tr><th>接口</th><th>set的行为</th><th>multiset的行为</th></tr></thead><tbody><tr><td>insert</td><td>插入重复元素时返回失败(仅插入一次)</td><td>插入重复元素时成功(可插入多次)</td></tr><tr><td>find</td><td>返回第一个匹配键的迭代器</td><td>返回第一个匹配键的迭代器(切记是中序遍历的第一个)</td></tr><tr><td>count</td><td>返回0或1(仅表示存在性)</td><td>返回键的实际出现次数</td></tr><tr><td>lower_bound/upper_bound</td><td>区间[lb, ub)长度最多为1</td><td>区间[lb, ub)包含所有匹配键的元素</td></tr><tr><td>erase</td><td>按键删除时,删除所有匹配的元素(仅1个)</td><td>按键删除时,删除所有匹配的元素(可能多个)</td></tr></tbody></table>
<p class="maodian"></p><h3>3.3 使用场景差异</h3>
<ul><li><code>set</code>:适用于<strong>需要唯一键</strong>的场景(如存储不重复的ID、去重后的数据集);</li><li><code>multiset</code>:适用于<strong>需要统计键出现次数</strong>的场景(如统计单词频率、存储可重复的有序数据)。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#include &lt;set&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
    // set:键唯一
    set&lt;int&gt; s = {1, 2, 2, 3};
    cout &lt;&lt; "set大小:" &lt;&lt; s.size() &lt;&lt; endl; // 输出3(自动去重)

    // multiset:键可重复
    multiset&lt;int&gt; ms = {1, 2, 2, 3};
    cout &lt;&lt; "multiset大小:" &lt;&lt; ms.size() &lt;&lt; endl; // 输出4(保留重复)

    // count接口差异
    cout &lt;&lt; "set中2的数量:" &lt;&lt; s.count(2) &lt;&lt; endl; // 输出1
    cout &lt;&lt; "multiset中2的数量:" &lt;&lt; ms.count(2) &lt;&lt; endl; // 输出2

    return 0;
}
</pre></div>
<p class="maodian"></p><h2>4. 例题部分</h2>
<p class="maodian"></p><h3>4.1 环形链表 II</h3>
<p>题目链接: 点此跳转</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340834.jpg" /></p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340845.png" /></p>
<p>我们之前C语言阶段是使用快慢指针完成的 其实我们可以用<code>ste&lt;Node*&gt; s</code>来做 遍历链表,每个节点是否在<code>s</code>中,不在就插入,在的第一个点就是入口点 , 要说这道题唯一的缺陷 就是有<span><span><span> O ( N ) O(N) </span><span><span><span>O</span><span>(</span><span>N</span><span>)</span></span></span></span></span>的空间复杂度。</p>
<div class="jb51code"><pre class="brush:cpp;">/**
* Definition for singly-linked list.
* struct ListNode {
*   int val;
*   ListNode *next;
*   ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode *detectCycle(ListNode* head)
    {
      set&lt;ListNode*&gt; s;
      ListNode* tmp=head;
      while(tmp!=NULL)
      {
            if(s.count(tmp)==0)
            {
                s.insert(tmp);
                tmp=tmp-&gt;next;
            }
            else
            {
                return tmp;
            }
      }
      return NULL;
    }
};
</pre></div>
<p class="maodian"></p><h3>4.2 两个数组的交集</h3>
<p>题目链接: 点此转跳</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340848.png" /></p>
<p>这题也挺简单的 其实就是拿<code>set</code>去重就可以了 然后用一个<code>set的count</code>去遍历另一个<code>set</code> 把重复的插入<code>vector</code>即可。</p>
<div class="jb51code"><pre class="brush:cpp;">class Solution {
public:
    vector&lt;int&gt; intersection(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2)
    {
   //去重
   set&lt;int&gt; s1(nums1.begin(),nums1.end());
   set&lt;int&gt; s2(nums2.begin(),nums2.end());
   vector&lt;int&gt; v;
   for(auto e : s1)
   {
      if(s2.count(e))
      {
            v.push_back(e);
      }
   }
   return v;
    }
};
</pre></div>
<p><strong>补充</strong>:<br />这么做 其实复杂度还是高的 因为<code>count</code>的特性 时间复杂度可能要<span><span><span> O ( N &lowast; l o g N ) O(N*logN) </span><span><span><span>O</span><span>(</span><span>N</span><span>&lowast;</span></span><span><span>l</span><span>o</span><span>g</span><span>N</span><span>)</span></span></span></span></span><br />但是利用<strong>双指针特性</strong>就可以把复杂度压缩到<span><span><span> O ( N ) O(N) </span><span><span><span>O</span><span>(</span><span>N</span><span>)</span></span></span></span></span>。这个方法不光能找交集,也能找差集。</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121508340813.png" /></p>
<p>到此这篇关于C++ set和multiset的使用小结的文章就介绍到这了,更多相关C++ set和multiset内容请搜索琼殿技术社区以前的文章或继续浏览下面的相关文章希望大家以后多多支持琼殿技术社区!</p>
                           
                            <div class="art_xg">
                              <b>您可能感兴趣的文章:</b><ul><li>C++map,set,multiset,multimap详细解析</li><li>C++中set/multiset与map/multimap的使用详解</li><li>C++中set/multiset容器详解(附测试用例与结果图)</li><li>C++ STL入门教程(7) multimap、multiset的使用</li></ul>
                            </div>

                        </div>
                        <!--endmain-->
頁: [1]
查看完整版本: C++ set和multiset的使用小结