Leetcode 3002. Maximum Size of a Set After Removals

• Leetcode 3002. Maximum Size of a Set After Removals
  • 1. 解题思路
  • 2. 代码实现
  • 3. 算法优化

• 题目链接：10037. Maximum Size of a Set After Removals

1. 解题思路

这一题的话我的思路就是分别以两个数组作为主数组，然后从中选择$n/2$个元素，并使得另一个数组当中不包含这些数字，然后考察剩下的那个数组当中可以保留下多少数字，两者加和即可得到对应取法下的最大值。

对此，我们只需要先将主数组当中的元素按照另一个数组当中出现的频次进行排序然后顺序选取即可。

然后，我们从最后的两个答案当中选出最大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        
        cnt1 = Counter(nums1)
        cnt2 = Counter(nums2)
        set1 = set(nums1)
        set2 = set(nums2)
        
        s1 = sorted(set1, key=lambda x: cnt2[x])[:n//2]
        s2 = set2 - set(s1)
        ans1 = len(s1) + min(len(s2), n//2)
        
        s2 = sorted(set2, key=lambda x: cnt1[x])[:n//2]
        s1 = set1 - set(s2)
        ans2 = min(len(s1), n//2) + len(s2)
        
        return max(ans1, ans2)

提交代码评测得到：耗时604ms，占用内存29.8MB。

3. 算法优化

看了一下大佬们的解答，发现他们的思路更加直接一点，其实也是我最开始的思路，不过后来我想岔了，还以为会有特殊情况……

简单来说，就是分别从两个数组当中选出所有的只出现在一个数组当中的元素，然后拼接上剩余那些在两个数组当中都有出现的数组，拼接到最终的$n$个元素即可。

给出python代码实现如下：

class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        N = len(nums1)
        nums1, nums2 = set(nums1), set(nums2)
        both = nums1 & nums2
        one = nums1 ^ both
        two = nums2 ^ both
        from_one = min(N//2, len(one))
        from_two = min(N//2, len(two))
        return min(from_one + from_two + len(both), N)

提交代码评测得到：耗时498ms，占用内存30MB。