【Leetcode】移除后集合的最多元素数
2024-01-08 00:47:03
目录
💡题目描述
给你两个下标从 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.? ?返回经过以上处理后的最大可能元素数量
主要步骤如下:
- 将nums1和nums2中的元素分别放入set1和set2
- 统计set1大小n1,set2大小n2,公共元素数量common
- 总元素数量为n1+n2-common
- 定义长度一半为m
- 如果set1大于m,答案和common分别减去set1大于m的部分
- 如果set2大于m,也进行同样减法
- 返回答案
所以这道题是通过无序集合统计元素情况,并考虑是否需要移除长度一半的元素后,返回集合s可能包含的最大元素数量。
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;
}
};
💡总结
主要步骤:
- 使用unordered_set存储nums1和nums2元素
- 统计set1,set2大小和公共元素数量
- 初始答案为set1+set2-公共元素
- 定义长度一半为m
- 如果set大小大于m,答案和公共元素分别减去大于m部分
- 返回最终答案
总的来说就是利用无序集合统计元素情况,并考虑是否需要移除长度一半元素来返回最大可能元素数量。
文章来源:https://blog.csdn.net/w050423/article/details/135440333
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!