题目练习之set的奇妙使用

用户11352420

发布于 2025-04-08 08:46:49

1030

上一篇博客我们已经对set容器进行了详细的介绍，相信大家对set有了更加深刻的认识，光说不练假把式，这一篇博客我们就来使用set容器在我们的算法题大放异彩~准备好了吗~我们发车去探索C++的奥秘啦~🚗🚗🚗🚗🚗🚗

两个数组的交集

    按照我们以前的思路我们可以新建一个数组，然后遍历原来的两个数组，找到重复元素保存到新数组里面~

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) 
{
int i=0;
int j=0;
int k=0;
int count=0;
int*arr=(int*)malloc(sizeof(int)*1000);
for (i = 0; i < nums1Size; i++)
{
    int flag = 1;
    for (j = 0; j < nums2Size; j++)
    {
        if (nums1[i] == nums2[j])
        {
            for (k = 0; k <= count; k++)
            {
                if (arr[k] == nums1[i])
                {
                    flag = 0;
                        break;
                }
            }
            if (flag != 0)
            {
                arr[count] = nums1[i];
                count++;
            }
            break;
        }
    }
}
 *returnSize=count;
 return arr;
}

    现在有了set容器，我们就可以采用新思路：

1、分别使用两个set容器保存两个数组元素，这就完成了去重+排序的功能，我们后面也就不需要处理重复的问题~ 2、使用迭代器遍历容器，这里有两种情况如果相等就保存到返回的数组中，迭代器都++ 如果不相等就让元素小的那个迭代器进行++

class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        //使用set保存数据
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());

        vector<int> ret;

        //使用迭代器遍历
        auto it1=s1.begin();
        auto it2=s2.begin();

        while(it1 != s1.end() && it2 != s2.end())
        //一个走到末尾就结束
        {
            //如果相等保存数据，然后都++
            if(*it1==*it2)
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
            //不相等，小的++
            else if(*it1 < *it2)
            {
                it1++;
            }
            else if(*it1 > *it2)
            {
                it2++;
            }
        }
        return ret;
    }
};

成功通过，并且时间复杂度也十分优秀~

环形链表Ⅱ

这个题目我们也使用C语言做过，可以看看这篇博客的代码题目练习之链表那些事儿（再续）

可以看出当时思路还是比较复杂的，还需要进行证明才得出来思路，现在有了set容器，我们就可以降维打击了~

新思路：使用set容器保存结点指针，使用set的count进行计数，如果它已经有了，说明结点指针重复，那么这就是一个环形链表，当前结点指针就是第一个入环的，直接返回；如果没有插入set，继续遍历~

/**
 * 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)
        {
            //如果有就成环了，直接返回
            if(s.count(cur)) return cur;
            //如果没有，插入容器继续遍历
            s.insert(cur);
            cur=cur->next;
        }
        //走到结束
        return nullptr;
    }
};

成功通过，我们可以看到这个set的妙处就更加明显啦~

当然，我们除了使用count判断，还可以使用insert的返回值进行判断，前面我们说set容器insert接口返回值类型是pair类型，第二个是bool类型的，如果返回的是false说明插入失败，那么这就是第一个入环结点了~

/**
 * 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)
        {
            //根据insert返回值判断
            if(s.insert(cur).second==false) 
                        return cur;
            cur=cur->next;
        }
        //走到结束
        return nullptr;
    }
};