class Solution {
public:
int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {
}
};
3002. 移除后集合的最多元素数
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们的长度都是偶数 n 。
你必须从 nums1 中移除 n / 2 个元素，同时从 nums2 中也移除 n / 2 个元素。移除之后，你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。
返回集合 s可能的 最多 包含多少元素。
示例 1：
输入：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 个元素。
示例 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 个元素。
示例 3：
输入：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.length1 <= n <= 2 * 104n是偶数。1 <= nums1[i], nums2[i] <= 109原站题解
cpp 解法, 执行用时: 292 ms, 内存消耗: 124.4 MB, 提交时间: 2024-01-14 12:40:40
class Solution {
public:
int maximumSetSize(vector<int> &nums1, vector<int> &nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> set2(nums2.begin(), nums2.end());
int all = set1.size() + set2.size();
for (int x : set1) {
all -= set2.count(x); // 去掉重复的
}
int n = nums1.size();
int c1 = min((int) set1.size(), n / 2);
int c2 = min((int) set2.size(), n / 2);
return min(all, c1 + c2);
}
int maximumSetSize2(vector<int> &nums1, vector<int> &nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> set2(nums2.begin(), nums2.end());
int common = 0;
for (int x : set1) {
common += set2.count(x);
}
int n = nums1.size();
int c1 = min((int) set1.size() - common, n / 2);
int c2 = min((int) set2.size() - common, n / 2);
return min(n, c1 + c2 + common);
}
int maximumSetSize3(vector<int> &nums1, vector<int> &nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> set2(nums2.begin(), nums2.end());
int common = 0;
for (int x : set1) {
common += set2.count(x);
}
int n1 = set1.size();
int n2 = set2.size();
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;
}
};
java 解法, 执行用时: 26 ms, 内存消耗: 53.3 MB, 提交时间: 2024-01-14 12:39:45
class Solution {
public int maximumSetSize(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int x : nums1) {
set1.add(x);
}
Set<Integer> set2 = new HashSet<>();
for (int x : nums2) {
set2.add(x);
}
int common = 0;
for (int x : set1) {
if (set2.contains(x)) {
common++;
}
}
int n1 = set1.size();
int n2 = set2.size();
int ans = n1 + n2 - common;
int m = nums1.length / 2;
if (n1 > m) {
int mn = Math.min(n1 - m, common);
ans -= n1 - mn - m;
common -= mn;
}
if (n2 > m) {
n2 -= Math.min(n2 - m, common);
ans -= n2 - m;
}
return ans;
}
public int maximumSetSize2(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int x : nums1) {
set1.add(x);
}
Set<Integer> set2 = new HashSet<>();
int common = 0;
for (int x : nums2) {
if (set2.contains(x)) {
continue;
}
set2.add(x);
// 相比方法一，这样写会略快一点
if (set1.contains(x)) {
common++;
}
}
int n = nums1.length;
int c1 = Math.min(set1.size() - common, n / 2);
int c2 = Math.min(set2.size() - common, n / 2);
return Math.min(n, c1 + c2 + common);
}
public int maximumSetSize3(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int x : nums1) {
set1.add(x);
}
int all = set1.size();
Set<Integer> set2 = new HashSet<>();
for (int x : nums2) {
if (set2.contains(x)) {
continue;
}
set2.add(x);
if (!set1.contains(x)) {
all++;
}
}
int n = nums1.length;
int c1 = Math.min(set1.size(), n / 2);
int c2 = Math.min(set2.size(), n / 2);
return Math.min(all, c1 + c2);
}
}
golang 解法, 执行用时: 152 ms, 内存消耗: 7.7 MB, 提交时间: 2024-01-14 12:38:49
func maximumSetSize(nums1, nums2 []int) int {
set1 := map[int]bool{}
for _, x := range nums1 {
set1[x] = true
}
all := len(set1)
set2 := map[int]bool{}
for _, x := range nums2 {
if set2[x] {
continue
}
set2[x] = true
if !set1[x] {
all++
}
}
n := len(nums1)
c1 := min(len(set1), n/2)
c2 := min(len(set2), n/2)
return min(all, c1+c2)
}
func maximumSetSize2(nums1, nums2 []int) int {
set1 := map[int]bool{}
for _, x := range nums1 {
set1[x] = true
}
set2 := map[int]bool{}
common := 0
for _, x := range nums2 {
if set2[x] {
continue
}
set2[x] = true
// 另一种求 common 的写法
if set1[x] {
common++
}
}
n := len(nums1)
c1 := min(len(set1)-common, n/2)
c2 := min(len(set2)-common, n/2)
return min(n, c1+c2+common)
}
func maximumSetSize3(nums1, nums2 []int) int {
set1 := map[int]bool{}
for _, x := range nums1 {
set1[x] = true
}
set2 := map[int]bool{}
for _, x := range nums2 {
set2[x] = true
}
common := 0
for x := range set1 {
if set2[x] {
common++
}
}
n1 := len(set1)
n2 := len(set2)
ans := n1 + n2 - common
m := len(nums1) / 2
if n1 > m {
mn := min(n1-m, common)
ans -= n1 - mn - m
common -= mn
}
if n2 > m {
n2 -= min(n2-m, common)
ans -= n2 - m
}
return ans
}
func min(a, b int) int { if a < b { return a }; return b }
python3 解法, 执行用时: 84 ms, 内存消耗: 26.4 MB, 提交时间: 2024-01-14 12:37:34
class Solution:
# 优先移除交集元素
def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
set1 = set(nums1)
set2 = set(nums2)
common = len(set1 & set2)
n1 = len(set1)
n2 = len(set2)
ans = n1 + n2 - common
m = len(nums1) // 2
if n1 > m: # nums1去重后数量大于要移除的数量
mn = min(n1 - m, common)
ans -= n1 - mn - m
common -= mn
if n2 > m:
n2 -= min(n2 - m, common)
ans -= n2 - m
return ans
# 从添加的角度看
def maximumSetSize2(self, nums1: List[int], nums2: List[int]) -> int:
set1 = set(nums1)
set2 = set(nums2)
common = len(set1 & set2)
n = len(nums1)
c1 = min(len(set1) - common, n // 2)
c2 = min(len(set2) - common, n // 2)
return min(n, c1 + c2 + common)
def maximumSetSize3(self, nums1: List[int], nums2: List[int]) -> int:
set1 = set(nums1)
set2 = set(nums2)
n = len(nums1)
c1 = min(len(set1), n // 2)
c2 = min(len(set2), n // 2)
return min(len(set1 | set2), c1 + c2)