算法 【Leetcode】移除后集合的最多元素数

目录

题目描述

思路

总结

100150. 移除后集合的最多元素数

题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们的长度都是偶数 n 。

你必须从 nums1 中移除 n / 2 个元素，同时从 nums2 中也移除 n / 2 个元素。移除之后，你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。

返回集合 s可能的 最多 包含多少元素。

思路

这道题是求两个数组 nums1 和 nums2 各移除长度的一半元素后，剩余元素组成的集合s可能包含的最大元素数量。

主要思路是：

1.  将nums1和nums2中的元素分别放入两个无序集set1和set2中，统计两个集合的大小n1和       n2,以及公共元素数量common

2.  计算如果不移除任何元素，集合s可能包含的最大元素数量为n1+n2-common

3.  考虑是否需要从set1和set2中各移除长度一半的元素：

如果set1大小大于长度一半，从答案和公共元素中分别减去set1大于长度一半的部分如果set2大小大于长度一半，也进行同样的减法操作

4.   返回经过以上处理后的最大可能元素数量

主要步骤如下：

将nums1和nums2中的元素分别放入set1和set2统计set1大小n1,set2大小n2,公共元素数量common总元素数量为n1+n2-common定义长度一半为m如果set1大于m,答案和common分别减去set1大于m的部分如果set2大于m,也进行同样减法返回答案

所以这道题是通过无序集合统计元素情况，并考虑是否需要移除长度一半的元素后，返回集合s可能包含的最大元素数量。

class Solution {

public:

int maximumSize(vector& nums1, vector& nums2) {

unordered_set set1, set2;

for(int num: nums1) set1.insert(num);

for(int num: nums2) set2.insert(num);

int n1 = set1.size(), n2 = set2.size();

int common = 0;

for(int num: set1) {

if(set2.count(num)) common++;

}

int ans = n1 + n2 - common;

int m = nums1.size()/2;

if(n1 > m) {

int mn = min(n1-m, common);

ans -= n1 - mn - m;

common -= mn;

}

if(n2 > m) {

n2 -= min(n2-m, common);

ans -= n2 - m;

}

return ans;

}

};

总结

主要步骤：

使用unordered_set存储nums1和nums2元素统计set1,set2大小和公共元素数量初始答案为set1+set2-公共元素定义长度一半为m如果set大小大于m,答案和公共元素分别减去大于m部分返回最终答案

总的来说就是利用无序集合统计元素情况，并考虑是否需要移除长度一半元素来返回最大可能元素数量。

精彩文章

 您阅读本篇文章共花了：