Medium

题目描述

给你两个下标从 0 开始、长度为偶数 n 的整数数组 nums1 和 nums2 。

你必须从 nums1 中移除 n / 2 个元素，从 nums2 中也移除 n / 2 个元素。移除后，你将剩余元素插入到集合 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}。
可以证明 2 是移除后集合 s 的最大可能大小。

示例 2：

输入：nums1 = [1,2,3,4,5,6], nums2 = [2,3,2,3,2,3]
输出：5
解释：我们从 nums1 中移除 2、3 和 6，从 nums2 中移除 2 和两个 3。移除后，数组变为 nums1 = [1,4,5] 和 nums2 = [2,3,2]。因此，s = {1,2,3,4,5}。
可以证明 5 是移除后集合 s 的最大可能大小。

示例 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}。
可以证明 6 是移除后集合 s 的最大可能大小。

提示：

  • n == nums1.length == nums2.length
  • 1 <= n <= 2 * 10^4
  • n 是偶数
  • 1 <= nums1[i], nums2[i] <= 10^9

解题思路

这道题的关键是理解我们需要从两个数组中各保留 n/2 个元素，使得最终集合的大小最大。

贪心策略分析：

为了最大化集合大小，我们应该优先保留那些能为集合贡献独特元素的数字。具体策略如下：

  1. 分类元素：将所有元素分为三类：

    • 只在 nums1 中出现的独特元素
    • 只在 nums2 中出现的独特元素
    • 同时在两个数组中出现的公共元素

  2. 贪心选择：

    • 优先从每个数组中选择该数组的独特元素，因为这些元素只能从对应数组获得
    • 当独特元素不足 n/2 个时，再从公共元素中补充
    • 公共元素可以从任意一个数组中选择，所以我们灵活分配

  3. 计算步骤：

    • 设 nums1 独特元素数量为 unique1，nums2 独特元素数量为 unique2
    • 设公共元素数量为 common
    • nums1 最多能贡献 min(unique1, n/2) + max(0, n/2 - unique1) 个不同元素
    • nums2 最多能贡献 min(unique2, n/2) + max(0, n/2 - unique2) 个不同元素
    • 最终答案受限于总的不同元素数量

这个贪心策略保证了我们能获得最大的集合大小。

代码实现

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 n = nums1.size();
        int half = n / 2;
        
        // 计算独特元素和公共元素数量
        int unique1 = 0, unique2 = 0, common = 0;
        unordered_set<int> all_elements;
        
        for (int num : set1) {
            all_elements.insert(num);
            if (set2.find(num) == set2.end()) {
                unique1++;
            } else {
                common++;
            }
        }
        
        for (int num : set2) {
            all_elements.insert(num);
            if (set1.find(num) == set1.end()) {
                unique2++;
            }
        }
        
        // 计算每个数组能贡献的最大不同元素数
        int contrib1 = min(unique1, half) + min(common, half - min(unique1, half));
        int contrib2 = min(unique2, half) + min(common, half - min(unique2, half));
        
        return min((int)all_elements.size(), contrib1 + contrib2);
    }
};

class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        set1 = set(nums1)
        set2 = set(nums2)
        
        n = len(nums1)
        half = n // 2
        
        # 计算独特元素和公共元素
        unique1 = len(set1 - set2)  # 只在set1中的元素
        unique2 = len(set2 - set1)  # 只在set2中的元素
        common = len(set1 & set2)   # 公共元素
        
        # 计算每个数组能贡献的最大不同元素数
        contrib1 = min(unique1, half) + min(common, half - min(unique1, half))
        contrib2 = min(unique2, half) + min(common, half - min(unique2, half))
        
        # 总的不同元素数量
        total_unique = unique1 + unique2 + common
        
        return min(total_unique, contrib1 + contrib2)

public class Solution {
    public int MaximumSetSize(int[] nums1, int[] nums2) {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        
        int n = nums1.Length;
        int half = n / 2;
        
        // 计算独特元素和公共元素数量
        int unique1 = 0, unique2 = 0, common = 0;
        var allElements = new HashSet<int>();
        
        foreach (int num in set1) {
            allElements.Add(num);
            if (!set2.Contains(num)) {
                unique1++;
            } else {
                common++;
            }
        }
        
        foreach (int num in set2) {
            allElements.Add(num);
            if (!set1.Contains(num)) {
                unique2++;
            }
        }
        
        // 计算每个数组能贡献的最大不同元素数
        int contrib1 = Math.Min(unique1, half) + Math.Min(common, half - Math.Min(unique1, half));
        int contrib2 = Math.Min(unique2, half) + Math.Min(common, half - Math.Min(unique2, half));
        
        return Math.Min(allElements.Count, contrib1 + contrib2);
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maximumSetSize = function(nums1, nums2) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    
    const n = nums1.length;
    const half = Math.floor(n / 2);
    
    // 计算独特元素和公共元素数量
    let unique1 = 0, unique2 = 0, common = 0;
    const allElements = new Set();
    
    for (const num of set1) {
        allElements.add(num);
        if (!set2.has(num)) {
            unique1++;
        } else {
            common++;
        }
    }
    
    for (const num of set2) {
        allElements.add(num);
        if (!set1.has(num)) {
            unique2++;
        }
    }
    
    // 计算每个数组能贡献的最大不同元素数
    const contrib1 = Math.min(unique1, half) + Math.min(common, half - Math.min(unique1, half));
    const contrib2 = Math.min(unique2, half) + Math.min(common, half - Math.min(unique2, half));
    
    return Math.min(allElements.size, contrib1 + contrib2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是数组的长度。时间复杂度主要来自于创建集合和遍历元素，空间复杂度来自于存储去重后的元素集合。

相关题目