移除后集合的最多元素数

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.

Return the maximum possible size of the set s.

 

Example 1:

Input: nums1 = [1,2,1,2], nums2 = [1,1,1,1]
Output: 2
Explanation: 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 2 is the maximum possible size of the set s after the removals.

Example 2:

Input: nums1 = [1,2,3,4,5,6], nums2 = [2,3,2,3,2,3]
Output: 5
Explanation: 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 5 is the maximum possible size of the set s after the removals.

Example 3:

Input: nums1 = [1,1,2,2,3,3], nums2 = [4,4,5,5,6,6]
Output: 6
Explanation: 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 6 is the maximum possible size of the set s after the removals.

 

Constraints:

• n == nums1.length == nums2.length
• 1 <= n <= 2 * 104
• n is even.
• 1 <= nums1[i], nums2[i] <= 109

/*
题目思路：
1. 找出 nums1 和 nums2 中每个元素的出现次数。
2. 将两个数组合并成一个数组。
3. 按元素出现频率从低到高排序。
4. 移除频率最高的 n/2 个元素。
5. 返回剩余元素组成的集合的大小。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
    public int maxDistinctElements(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<Integer, Long> freqMap = Stream.concat(Arrays.stream(nums1).boxed(), Arrays.stream(nums2).boxed())
                .collect(Collectors.groupingBy(e -> e, Collectors.counting()));
        List<Map.Entry<Integer, Long>> freqList = freqMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue())
                .collect(Collectors.toList());
        Set<Integer> resultSet = new HashSet<>();
        int toRemove = n;
        for (Map.Entry<Integer, Long> entry : freqList) {
            if (toRemove <= 0) break;
            toRemove -= entry.getValue();
        }
        freqList.stream()
                .filter(entry -> entry.getValue() <= toRemove)
                .forEach(entry -> resultSet.add(entry.getKey()));
        return resultSet.size();
    }
}

首先，将nums1和nums2转换为集合set1和set2，以去除重复元素。然后，计算两个集合的交集大小（common）。接下来，计算每个集合的元素数量（n1和n2）。定义m为需要从每个数组中移除的元素数量（即n/2）。初始答案（ans）设置为n1 + n2 - common，代表了如果没有交集元素重叠，集合s能包含的最大元素数。接下来的逻辑是调整答案以考虑在移除元素时可能需要删除一些重复的元素。如果集合1的元素数n1大于m，那么可能需要从集合1中删除一些元素以满足移除要求，同时也可能需要从交集中减去一些重复的元素。同样的逻辑也适用于集合2。最终返回调整后的ans。

O(n)

O(n)