C++（初階）（十六）—

C++（初階）（十六）——set

set

set
- set介紹
- set的構造和迭代器
- set的增刪查
- - find
  - lower_bound
  - multiset和set的差異
- 題目
- - [349. 兩個數組的交集 - 力扣（LeetCode）](https://leetcode.cn/problems/intersection-of-two-arrays/description/)
  - 交集
  - 差集
  - [142. 環形鏈表 II - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle-ii/description/)

set介紹

1，set的聲明如下，T就是set底層關鍵字的類型

2，set默認要求T?持?于?較，如果不?持或者想按??的需求?可以??實現仿函數傳給第?個模版參數

3，set底層存儲數據的內存是從空間配置器申請的，如果需要可以??實現內存池，傳給第三個參數。

4，?般情況下，我們都不需要傳后兩個模版參數。

5，set底層是?紅?樹實現，增刪查效率是O(logN) ，迭代器遍歷是?的搜索樹的中序，所以是有序的。

6，前?部分我們已經學習了vector/list等容器的使?，STL容器接?設計，?度相似，所以這?我們就不再?個接??個接?的介紹，?是直接帶著?家看?檔，挑?較重要的接?進?介紹。

7，set是會去重的，所以刪除數據時，沒有使用bool值，而是int值。

set的構造和迭代器

set的?持正向和反向迭代遍歷，遍歷默認按升序順序，因為底層是?叉搜索樹，迭代器遍歷?的中序；

?持迭代器就意味著?持范圍for，set的iterator和const_iterator都不?持迭代器修改數據，修改關鍵字數據，破壞了底層搜索樹的結構。

// empty (1) 
?參默認構造explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 
迭代器區間構造template <class InputIterator>set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());// copy (3) 
拷?構造set (const set& x);// initializer list (5) initializer 
列表構造set (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());//迭代器是?個雙向迭代器
//正向迭代器
iterator   -> a bidirectional iterator to const value_type
iterator begin();
iterator end();//反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

set的增刪查

find

算法庫中實現的查找是迭代器遍歷，時間復雜度是O（n）

set內部實現的查找與樹的高度有關，時間復雜度是O（logn）

count返回一個數據在set中的個數，但是set會去重，所以返回值是0或1，也是int值。

	set<int> s = { 2,3,1,7,1,1,5 };for (auto e : s){cout << e << " ";}cout << endl;//直接刪除值為val的數據，不存在返回0s.erase(1);for (auto e : s){cout << e << " ";}cout << endl;//直接查找在利?迭代器刪除valauto pos = s.find(3);if (pos != s.end()){s.erase(pos);}for (auto e : s){cout << e << " ";}cout << endl;//利?count間接實現快速查找int x = 7;if (s.count(x)){cout << x << "存在" << endl;}else{cout << x << "不存在" << endl;}

lower_bound

//返回?于等val位置的迭代器
iterator lower_bound (const value_type& val) const;

//返回?于val位置的迭代器
iterator upper_bound (const value_type& val) const;

算法庫中也有lower_bound，upper_bound，但是要求是要對容器區間排序。
注意所得區間是左閉右開[lower,upper)

如果所給val > set.end();會返回set.end();的值

	set<int> myset = { 10,20,30,40,50,60,70,80,90 };for (auto e : myset){cout << e << " ";}cout << endl;//返回 >= 30位置的迭代器auto low = myset.lower_bound(30);//返回 > 70位置的迭代器，如果所給val > myset.end();會返回myset.end();的值auto up = myset.upper_bound(70);//使用迭代器打印[30,70)區間的值auto it = low;while (it != up){cout << *it << " ";++it;}cout << endl;//刪除[30,70)區間的值myset.erase(low, up);for (auto e : myset){cout << e << " ";}cout << endl;

multiset和set的差異

使用multiset，頭文件依然是#include< set >，不需要其他頭文件

multiset不會進行去重操作。

在進行查找操作時，查找到數據是中序遍歷的第一個數據。

題目

349. 兩個數組的交集 - 力扣（LeetCode）

給定兩個數組 nums1 和 nums2 ，返回 它們的交集 。輸出結果中的每個元素一定是唯一的。我們可以 不考慮輸出結果的順序 。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]

示例 2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
解釋：[4,9] 也是可通過的

去重：unique（算法庫中）；set都可以

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// set<int> s1;// for(auto e : nums1)// {//     s1.insert(e);// }// set<int> s2;// for(auto e : nums2)// {  //     s2.insert(e);// }//迭代器區間構造比較方便set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());vector<int> v;for(auto e : s1){//在set中count的返回值是1或0，如果s1中的數據在s2中也存在，就是交集if(s2.count(e)){v.push_back(e);}}return v;}
};

除此之外，還有方法能求交集，當然也可以帶入求差集。

并集是直接遍歷插入set< >即可，set< >會去重

交集

	vector<int> nums1 = { 1,3,5,6,7,8,9 };vector<int> nums2 = { 1,2,3,4,6 };vector<int> ret;//去重+排升序set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());//遍歷比較auto it1 = s1.begin();auto it2 = s2.begin();while (it1 != s1.end() && it2 != s2.end()){if (*it1 < *it2){++it1;}else if (*it1 > *it2){++it2;}else{//ret.push_back(*it1);ret.push_back(*it2);++it1;++it2;}}for (auto e : ret){cout << e << " ";}cout << endl;

差集

	vector<int> nums1 = { 1,3,5,6,7,8,9 };vector<int> nums2 = { 1,2,3,4,6 };vector<int> ret;//去重+排升序set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());//遍歷比較auto it1 = s1.begin();auto it2 = s2.begin();while (it1 != s1.end() && it2 != s2.end()){if (*it1 < *it2){ret.push_back(*it1);++it1;}else if (*it1 > *it2){ret.push_back(*it2);++it2;}else{++it1;++it2;}}//剩余值繼續記錄while (it1 != s1.end()){ret.push_back(*it1);++it1;}while (it2 != s2.end()){ret.push_back(*it2);++it2;}for (auto e : ret){cout << e << " ";}cout << endl;

142. 環形鏈表 II - 力扣（LeetCode）

給定一個鏈表的頭節點 head ，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改 鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

/*** 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<ListNode*> s;ListNode* cur = head;while(cur){auto ret = s.insert(cur);if(ret.second == false)return cur;cur = cur->next;}return nullptr;}
};