每日一题：LeetCode-10037. 移除后集合的最多元素数

作者：半亩房顶

2024-01-08
北京
本文字数：1415 字
阅读完需：约 5 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-size-of-a-set-after-removals/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你两个下标从 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 * 104
n是偶数。
1 <= nums1[i], nums2[i] <= 109

思路

贪心的思维不用多说，大家都能想到。

我一开始是正向去除数据的思路，然后也没走对路子，陷入了一个牛角尖没能出来。那干脆换了方向，我不想怎么去除数据，转头去想着怎么选择数据。

问题就变成了：

在两个数组中分别拿出 n/2 个数字，求拿出不同数字的最大值。

这么想的话，问题就拆解成三个部分：

从nums1中拿出它独有的数字，最多n/2
从nums2中拿出它独有的数字，最多n/2
如果存在某个数组中独有数字不足n/2，那就从共有的数字中拿

前两个很容易算出来，第三个值稍微多了一个逻辑

n/2 - nums1拿出独有数字数 + n/2 - nums2拿出独有数字数。
同样有个上限，那就是共有数字的个数

代码基本已经出来了。老样子，细节在代码注释

代码

func maximumSetSize(nums1 []int, nums2 []int) int {    // 统计各自独有数量 和 共有元素数量    var numMap1 = make(map[int]int)    for _, v := range nums1 {        numMap1[v]++    }    var numMap2 = make(map[int]int)    for _, v := range nums2 {        numMap2[v]++    }
    common := 0    for k := range numMap1 {        if _, ok := numMap2[k]; ok {            common++        }    }    uniqueCount1 := len(numMap1) - common    uniqueCount2 := len(numMap2) - common
    n := len(nums1)    // 思路转变为从各自数组中拿取n/2, 最多能拿多少个    // 从数组1的独有数字中最多拿 uniqueCount1，或者 uniqueCount1 超过 n/2，则只能拿 n/2 个    from1 := min(uniqueCount1, n / 2)    // 数组2同理    from2 := min(uniqueCount2, n / 2)    // 如果不够再能从共有元素中拿  n-uniqueCount1-uniqueCount2 个，    // 可能等于0，但也可能大于0。不过最多common个，多了就是重复的了    fromCommon := min(n - from1 - from2, common)    return from1 + from2 + fromCommon}