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

发布时间:2024年01月09日

瑟瑟发抖

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;
    }
}

文章来源:https://blog.csdn.net/kangbin825/article/details/135485509
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。