深圳智慧建设控股有限公司网站,西青集团网站建设,成都设计院,做网站与数据库的关系Leetcode 2856. Minimum Array Length After Pair Removals 1. 解题思路2. 代码实现 题目链接#xff1a;2856. Minimum Array Length After Pair Removals
1. 解题思路
这一题思路而言个人觉得还是挺有意思的#xff0c;因为显然这道题没法直接用greedy的方法进行处理2856. Minimum Array Length After Pair Removals
1. 解题思路
这一题思路而言个人觉得还是挺有意思的因为显然这道题没法直接用greedy的方法进行处理考察下述两个例子即可
1,2,3,3,31,2,2,2,3
因此问题就在于如何去想一个方式使得构造方式可以最大化。
而我们处理这个的思路就是将其首先按照相同元素进行聚类然后找到某一个元素e使其满足
严格小于该元素的所有元素的总个数不超过总元素个数的一半严格小于该元素的所有元素的总个数加上上述元素的个数超过总元素个数的一半
此时我们可以将所有元素分成三个部分
小于元素e的元素总数记作a元素e的元素总数记作b大于元素e的元素总数记作c
此时我们只需要分类讨论即可
如果满足 a c ≤ b ac \leq b ac≤b那么可以组成的pair的最大数目一定是 a c ac ac如果满足 a c b ac b acb那么总可以合理分配元素e用作大数和小数的方式使得所有的数字应消尽消此时所有的数字最多剩下一个取决于总元数个数的奇偶性。
2. 代码实现
给出python代码实现如下
class Solution:def minLengthAfterRemovals(self, nums: List[int]) - int:n len(nums)cnt sorted(Counter(nums).items())s 0for k, v in cnt:if s v n / 2:s vcontinuer n - s - vif s r v:return v - s - relse:return n % 2提交代码评测得到耗时1170ms占用内存33.8MB。
