【教3妹学编程-算法题】移除后集合的最多元素数

3妹：好冷啊， 冻得瑟瑟发抖啦
2哥 : 这才哪跟哪，上海这几天温度算是高的啦。你看看哈尔滨，那才是冰城。
3妹：据说沈阳千名“搓澡大姨”支援哈尔滨？哈哈哈哈
2哥 : 就像今年的淄博烧烤，可能有炒作的成分
3妹：不不，是去年的了，今年已经24年啦。 2哥，你说哈尔滨最多能住多少人，这么多人涌入哈尔滨，能住的下嘛。
2哥：这个就不用担心啦，自然是住得下的。 说到最多住的人数，我们是不是又该做每日一题啦？刚好今天的题目是关于最多元素数的~

题目：

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

思路：

先移除每个数组中的重复元素，再考虑从剩下的数中移除元素。
详解见代码：

java代码：

class Solution {
    public int maximumSetSize(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        for (int x : nums1) {
            set1.add(x);
        }
        Set<Integer> set2 = new HashSet<>();
        for (int x : nums2) {
            set2.add(x);
        }
        int common = 0;
        for (int x : set1) {
            if (set2.contains(x)) {
                common++;
            }
        }

        int n1 = set1.size();
        int n2 = set2.size();
        int ans = n1 + n2 - common;

        int m = nums1.length / 2;
        if (n1 > m) {
            int mn = Math.min(n1 - m, common);
            ans -= n1 - mn - m;
            common -= mn;
        }

        if (n2 > m) {
            n2 -= Math.min(n2 - m, common);
            ans -= n2 - m;
        }

        return ans;
    }
}

代码007普通

打赏 收藏 海报 链接