You are given two 0-indexed integer arrays nums1 and nums2 of even length n.
You must remove n / 2 elements from nums1 and n / 2 elements from
nums2. After the removals, you insert the remaining elements of nums1 and
nums2 into a set s.
Input: nums1 =[1,2,1,2], nums2 =[1,1,1,1]Output: 2Explanation: We remove two occurences of 1 from nums1 and nums2. After the removals, the arrays become equal to nums1 =[2,2] and nums2 =[1,1]. Therefore, s ={1,2}.It can be shown that 2is the maximum possible size of the set s after the removals.
Input: nums1 =[1,2,3,4,5,6], nums2 =[2,3,2,3,2,3]Output: 5Explanation: We remove 2,3, and 6 from nums1, as well as 2 and two occurrences of 3 from nums2. After the removals, the arrays become equal to nums1 =[1,4,5] and nums2 =[2,3,2]. Therefore, s ={1,2,3,4,5}.It can be shown that 5is the maximum possible size of the set s after the removals.
Input: nums1 =[1,1,2,2,3,3], nums2 =[4,4,5,5,6,6]Output: 6Explanation: We remove 1,2, and 3 from nums1, as well as 4,5, and 6 from nums2. After the removals, the arrays become equal to nums1 =[1,2,3] and nums2 =[4,5,6]. Therefore, s ={1,2,3,4,5,6}.It can be shown that 6is the maximum possible size of the set s after the removals.
To maximize the size of the set after removals, we want to keep as many unique elements as possible. Since we must remove exactly half from each array, we should prioritize keeping unique elements from both arrays, avoiding overlap where possible.
classSolution {
public:int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), k = n /2;
unordered_set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());
int both =0;
for (int x : s1) if (s2.count(x)) both++;
int only1 = s1.size() - both, only2 = s2.size() - both;
int ans = min(2* k, only1 + only2 + min(both, k));
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
funcmaximumSetSize(nums1, nums2 []int) int {
n, k:= len(nums1), len(nums1)/2s1, s2:=map[int]struct{}{}, map[int]struct{}{}
for_, x:=rangenums1 { s1[x] = struct{}{} }
for_, x:=rangenums2 { s2[x] = struct{}{} }
both:=0forx:=ranges1 { if_, ok:=s2[x]; ok { both++ } }
only1:= len(s1) -bothonly2:= len(s2) -bothans:=only1+only2+ min(both, k)
ifans > 2*k { ans = 2*k }
returnans}
func min(a, bint) int { ifa < b { returna }; returnb }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
publicintmaximumSetSize(int[] nums1, int[] nums2) {
int n = nums1.length, k = n / 2;
Set<Integer> s1 =new HashSet<>();
Set<Integer> s2 =new HashSet<>();
for (int x : nums1) s1.add(x);
for (int x : nums2) s2.add(x);
int both = 0;
for (int x : s1) if (s2.contains(x)) both++;
int only1 = s1.size() - both, only2 = s2.size() - both;
int ans = only1 + only2 + Math.min(both, k);
return Math.min(ans, 2 * k);
}
}
1
2
3
4
5
6
7
8
9
10
classSolution {
funmaximumSetSize(nums1: IntArray, nums2: IntArray): Int {
val n = nums1.size; val k = n / 2val s1 = nums1.toSet(); val s2 = nums2.toSet()
val both = s1.count { itin s2 }
val only1 = s1.size - both; val only2 = s2.size - both
val ans = only1 + only2 + minOf(both, k)
return minOf(ans, 2 * k)
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
defmaximumSetSize(self, nums1: list[int], nums2: list[int]) -> int:
n = len(nums1)
k = n //2 s1 = set(nums1)
s2 = set(nums2)
both = len(s1 & s2)
only1 = len(s1) - both
only2 = len(s2) - both
ans = only1 + only2 + min(both, k)
return min(ans, 2* k)
1
2
3
4
5
6
7
8
9
10
11
12
13
impl Solution {
pubfnmaximum_set_size(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let n = nums1.len();
let k = n /2;
let s1: std::collections::HashSet<_>= nums1.iter().cloned().collect();
let s2: std::collections::HashSet<_>= nums2.iter().cloned().collect();
let both = s1.intersection(&s2).count();
let only1 = s1.len() - both;
let only2 = s2.len() - both;
let ans = only1 + only2 + std::cmp::min(both, k);
ans.min(2* k) asi32 }
}