题目描述
给你两个下标从 0 开始的整数数组 nums1
和 nums2
,它们的长度都是偶数 n
。
你必须从 nums1
中移除 n / 2
个元素,同时从 nums2
中也移除 n / 2
个元素。移除之后,你将 nums1
和 nums2
中剩下的元素插入到集合 s
中。
返回集合 s
可能的 最多 包含多少元素。
样例
输入:nums1 = [1,2,1,2], nums2 = [1,1,1,1]
输出:2
解释:从 nums1 和 nums2 中移除两个 1。
移除后,数组变为 nums1 = [2,2] 和 nums2 = [1,1]。
因此,s = {1,2}。
可以证明,在移除之后,集合 s 最多可以包含 2 个元素。
输入:nums1 = [1,2,3,4,5,6], nums2 = [2,3,2,3,2,3]
输出:5
解释:从 nums1 中移除 2、3 和 6,同时从 nums2 中移除两个 3 和一个 2。
移除后,数组变为 nums1 = [1,4,5] 和 nums2 = [2,3,2]。
因此,s = {1,2,3,4,5}。
可以证明,在移除之后,集合 s 最多可以包含 5 个元素。
输入:nums1 = [1,1,2,2,3,3], nums2 = [4,4,5,5,6,6]
输出:6
解释:从 nums1 中移除 1、2 和 3,同时从 nums2 中移除 4、5 和 6。
移除后,数组变为 nums1 = [1,2,3] 和 nums2 = [4,5,6]。
因此,s = {1,2,3,4,5,6}。
可以证明,在移除之后,集合 s 最多可以包含 6 个元素。
限制
n == nums1.length == nums2.length
1 <= n <= 2 * 10^4
n
是偶数。1 <= nums1[i], nums2[i] <= 10^9
算法
(思维题) $O(n)$
- 分别求出
nums1
和nums2
的集合s1
和s2
。 - 求出两个集合交集的大小
m
。 - 目标是保留两个数组中尽可能多的不同的数字,所以优先选择不在两个集合交集中的元素。
- 第一个数组中不在交集的元素个数 $t1$ 为 $n - s1.size$,如果 $t1$ 超过了 $n/2$,则最多只能选择 $n/2$ 个。第二个数组 $t2$ 同理。
- 最终可以选择不重复的数字个数为 $t1 + t2 + \min(n - t1 - t2, m)$,即两个数组如果有没选择够 $n/2$ 个元素,需要从交集中选择元素,但交集中最多只有 $m$ 个不同的元素。
时间复杂度
- 构造集合的时间复杂度为 $O(n)$,求交集的时间复杂度为 $O(n)$,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储两个集合。
C++ 代码
class Solution {
public:
int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {
const int n = nums1.size();
unordered_set<int> s1(nums1.begin(), nums1.end());
unordered_set<int> s2(nums2.begin(), nums2.end());
int n1 = s1.size(), n2 = s2.size();
int m = 0;
for (int x : s1)
if (s2.find(x) != s2.end())
++m;
int t1 = min(n / 2, n1 - m), t2 = min(n / 2, n2 - m);
return t1 + t2 + min(n - t1 - t2, m);
}
};