刷题使我快乐，满脸开心.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
}