前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【Leetcode】移除后集合的最多元素数

【Leetcode】移除后集合的最多元素数

作者头像
P_M_P
修改2024-01-19 10:04:36
1300
修改2024-01-19 10:04:36
举报

100150. 移除后集合的最多元素数

💡题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,它们的长度都是偶数 n 。 你必须从 nums1 中移除 n / 2 个元素,同时从 nums2 中也移除 n / 2 个元素。移除之后,你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。 返回集合 s可能的 最多 包含多少元素。

💡思路

这道题是求两个数组 nums1 和 nums2 各移除长度的一半元素后,剩余元素组成的集合s可能包含的最大元素数量。

主要思路是:

1. 将nums1和nums2中的元素分别放入两个无序集set1和set2中,统计两个集合的大小n1和 n2,以及公共元素数量common 2. 计算如果不移除任何元素,集合s可能包含的最大元素数量为n1+n2-common 3. 考虑是否需要从set1和set2中各移除长度一半的元素:

  • 如果set1大小大于长度一半,从答案和公共元素中分别减去set1大于长度一半的部分
  • 如果set2大小大于长度一半,也进行同样的减法操作

4. 返回经过以上处理后的最大可能元素数量

主要步骤如下:

  1. 将nums1和nums2中的元素分别放入set1和set2
  2. 统计set1大小n1,set2大小n2,公共元素数量common
  3. 总元素数量为n1+n2-common
  4. 定义长度一半为m
  5. 如果set1大于m,答案和common分别减去set1大于m的部分
  6. 如果set2大于m,也进行同样减法
  7. 返回答案

所以这道题是通过无序集合统计元素情况,并考虑是否需要移除长度一半的元素后,返回集合s可能包含的最大元素数量。

代码语言:javascript
复制
class Solution {
public:
    int maximumSize(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1, set2;
        
        for(int num: nums1) set1.insert(num);
        for(int num: nums2) set2.insert(num);
        
        int n1 = set1.size(), n2 = set2.size();
        int common = 0;
        
        for(int num: set1) {
            if(set2.count(num)) common++; 
        }
        
        int ans = n1 + n2 - common;
        int m = nums1.size()/2; 
        
        if(n1 > m) {
            int mn = min(n1-m, common);
            ans -= n1 - mn - m;
            common -= mn;
        }
        
        if(n2 > m) {
            n2 -= min(n2-m, common); 
            ans -= n2 - m;
        }
        
        return ans;
    }
};

💡总结

主要步骤:

  1. 使用unordered_set存储nums1和nums2元素
  2. 统计set1,set2大小和公共元素数量
  3. 初始答案为set1+set2-公共元素
  4. 定义长度一半为m
  5. 如果set大小大于m,答案和公共元素分别减去大于m部分
  6. 返回最终答案

总的来说就是利用无序集合统计元素情况,并考虑是否需要移除长度一半元素来返回最大可能元素数量。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-01-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 💡题目描述
  • 💡思路
  • 💡总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档