网站建设好还是阿里巴巴好,义乌建网站,网站制作公司 深圳,重庆网站建设技术支持Every day a Leetcode
题目来源#xff1a;3002. 移除后集合的最多元素数
解法1#xff1a;贪心
可以将数组去重后分为三个部分#xff1a;nums1 独有的#xff0c;nums2 独有的#xff0c;nums1 与 nums2 共有的。
求集合 S 时#xff1a;
先选择两个数组独有的。…Every day a Leetcode
题目来源3002. 移除后集合的最多元素数
解法1贪心
可以将数组去重后分为三个部分nums1 独有的nums2 独有的nums1 与 nums2 共有的。
求集合 S 时
先选择两个数组独有的。对于共有的两个数组尽量选不一样的。
代码
/** lc appleetcode.cn id10037 langcpp** [10037] 移除后集合的最多元素数*/// lc codestart
class Solution
{
public:int maximumSetSize(vectorint nums1, vectorint nums2){int n nums1.size();unordered_setint set1, set2;for (int x : nums1)set1.insert(x);for (int x : nums2)set2.insert(x);int common 0; // 两个数组共有的元素个数for (int x : set1)if (set2.count(x))common;// count1 和 count2 分别为数组 nums1 和 nums2 独有元素的个数int count1 set1.size() - common, count2 set2.size() - common;// 贪心策略先选二者独有的没得选才选二者共有的int s1 min(count1, n / 2), s2 min(count2, n / 2);return s1 s2 min(n - s1 - s2, common);}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是数组 nums1/nums2 的长度。
空间复杂度O(n)其中 n 是数组 nums1/nums2 的长度。
