与set和map相关的OJ题练习

一、两个数组的交集

题目链接：

349. 两个数组的交集 - 力扣（LeetCode）

题目描述：

给两个数组，求在数组里面共同出现的部分，就是求两个数组的交集，返回顺序不做要求

解题思路：

求交集问题，可以先对数据进行去重+升序排序，然后两个数组同时从第一个开始走，当数值相同，则说明是交集，输出并两个同时走下一个，若是不相同，则让小的那一个单独走到下一个，直到某一个走完，则结束。

参考代码：

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        //找交集先利用set去重加排序
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
        //升序序列找交集：相同，则为交集，不同，则小的往后走，其中一方结束则结束
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        vector<int> ret;
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 == *it2)
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
            else if(*it1 < *it2)
            {
                it1++;
            }
            else
            {
                it2++;
            }
        }
        return ret;
    }

二、前k个高频单词

题目链接：

692. 前K个高频单词 - 力扣（LeetCode）

题目描述：

题目给你一个vector类型，也就是单词序列，需要找到在序列中出现次数从多到少前k个单词，并且要求当单词出现次数相同时，要按照字典序排序，存入到一个vector中返回

解题思路：

利用map去对单词进行统计然后按字典序输出，存放到一个vector中，然后对序列中的单词根据次数进行排序，由于题目要求相同时按照字典序排序，因此，使用排序的时候要求不破坏前后顺序，也就是要求使用具有稳定性的排序去进行排序，可以使用算法中提供的排序，也可以利用仿函数给定排序规则去实现

参考代码：

    class Compare
    {
        public:
        bool operator()(const pairint>& x,const pairint>& y)const 
        {
            return x.second > y.second || (x.second == y.second && x.first < y.first);
        }
    };
 
    vector topKFrequent(vector& words, int k) 
    {
        //使用map去统计每个单词的次数
        mapint> map_count;
        for(auto& e:words)
        {
            map_count[e]++;
        }
        //此时输出的顺序是按照字典序输出的，将其存放到一个vector中，利用具有稳定性的方式按照次数排序即可
 
        vectorint>> v(map_count.begin(),map_count.end());
        sort(v.begin(),v.end(),Compare());
        vector ret;
        for(int i = 0;i
        {
            ret.push_back(v[i].first);
        }
        return ret;
    }

三、复杂链表的深拷贝

题目链接：

LCR 154. 复杂链表的复制 - 力扣（LeetCode）

题目描述：

题目给了一个单向的链表，比起普通单链表，还多了一个随机指针random，每个节点的随机指针都随机指向其他节点或者是自己，也可能是空，题目要求拷贝一条一模一样的链表，难点在于随机指针要完成深拷贝，需要原链表和拷贝链表建立某种联系，使得能够知道原链表的随机指针是如何指向的

解题思路：

在C语言阶段时，我们采用通过将每个拷贝节点链接在原节点的方式建立链接去确定random指针的指向，现在我们学习了map以后，可以直接通过map去建立原链表和拷贝链表之间的链接，然后去确定好random

参考代码：

    Node* copyRandomList(Node* head) 
    {
        //直接先拷贝一条链表
        Node* copy_head = nullptr;
        Node* copy_tail = nullptr;
        Node* cur = head;
        while(cur)
        {
            if(copy_head == nullptr)
            {
                copy_head = new Node(cur->val);
                copy_tail = copy_head;
            }
            else
            {
                Node* newnode = new Node(cur->val);
                copy_tail->next = newnode;
                copy_tail = newnode;
            }
            cur = cur->next;
        }
        //利用map建立两个链表之间的链接,并且通过原指针的random去找到copy后的random链接
        map m;
        Node* cur1 = head;
        Node* cur2 = copy_head;
        while(cur1)
        {
            m[cur1] = cur2;//建立链接
            cur1=cur1->next;
            cur2=cur2->next;
        }
        cur1 = head;
        cur2 = copy_head;
        while(cur1)
        {
            cur2->random = m[cur1->random];//通过联系链接
            cur1=cur1->next;
            cur2=cur2->next;
        }
        return copy_head;
    }