移除后集合的最多元素数

难度: Medium

给你两个下标从 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.length
1 <= n <= 2 * 10⁴
n是偶数。
1 <= nums1[i], nums2[i] <= 10⁹

Submission

运行时间: 50 ms

内存: 25.4 MB

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)

        m = len(nums1) // 2

        ans = n1 + n2 - common


        if n1 > m:
            mn = min(n1 - m, common)
            n1 -= mn
            common -= mn
            ans -= n1 - m

        if n2 > m:
            mn = min(n2 - m, common)
            n2 -= mn
            ans -= n2 - m

        return ans

Explain

首先，将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)


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)

        # 需要移除的元素数量
        m = len(nums1) // 2

        # 初始可能的最大元素数量
        ans = n1 + n2 - common

        # 调整n1和common以满足移除要求
        if n1 > m:
            mn = min(n1 - m, common)
            n1 -= mn
            common -= mn
            ans -= n1 - m

        # 调整n2以满足移除要求
        if n2 > m:
            mn = min(n2 - m, common)
            n2 -= mn
            ans -= n2 - m

        # 返回调整后的最大可能元素数量
        return ans

Explore

将nums1和nums2转换成集合set1和set2主要是为了去除各自数组中的重复元素。这样做不仅简化了后续的计算，因为集合不包含重复元素，而且使得计算两个数组的交集、并集等集合操作变得更加直接和高效。此外，这也有助于更准确地估计在移除一定数量元素后所能达到的最大不重复元素的数量。

这种计算方式基于集合的基本理论。其中，n1和n2分别是集合set1和set2的元素数量，而common是这两个集合的交集元素数量。在不考虑任何元素移除的情况下，两个集合合并的总元素数为n1 + n2。然而，因为交集中的元素在两个集合中都出现过，所以被重复计算了一次，故需要从总数中减去这部分重复计算的元素数量（common），以得到合并后不重复的元素总数。这个计算提供了一个没有元素移除时的最大可能元素数量的初始估计。

算法中，需要删除的元素数量基于每个集合的元素数量与m（即每个数组的一半长度）的比较来确定。如果一个集合的元素数量超过了m，那么就需要将集合的元素数量减少到m。算法尝试从交集中优先移除重复元素，以尽量减少对最大元素数量的影响。此逻辑确保了在给定的移除限制下，尽可能保留最多的不重复元素，但是否是绝对最优解可能需要更详细的分析或实际的例子来验证，因为复杂的交集和不同大小的集合可能影响最终的结果。

从交集中减去重复的元素是为了确保在满足移除要求的同时，最大化保留不同的元素。由于交集的元素在两个集合中都存在，如果不从交集中移除重复元素，那么这些元素在计算最终元素总数时会被重复计算。因此，通过减少交集的重复元素，可以更有效地利用每个集合独有的元素来增加最终集合的元素多样性。这一步骤是优化元素总数的关键，尤其是在有严格的元素移除限制时。