当前位置：首页 > article >正文

leetcode 2856. 删除数对后的最小数组长度

article 2025/2/3 18:53:54

题目如下
在这里插入图片描述
数据范围

示例

我们假设存在一个出现频率最高的数a那么我们可以把这个数组分成三部分那么第一部分和第三部分必然可以消去一部分 然后它们剩下的和a再消去
当a的数量是数组的一半那么显然剩下的就是0
当a的数量大于数组的一半那么显然存在无法消去的a 剩2 * count - n
当a的数量小于数组的一半1.当n为偶数（可以画图因为a不足一半就意味着当数组分成两组时a不会相互重叠例如  0 1 2 2 3 4 中2不重叠 或者可以用第一部分消去第三部分会刚好剩下a的数量个数然后再和a消）那么可以消去全部即剩0
										  2.当n为奇数 同上剩1
											即取决于n的奇偶性

通过代码

class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        int n = nums.size();
        int ans = n % 2;
        int count = ranges::upper_bound(nums,nums[n/2]) - ranges::lower_bound(nums,nums[n/2]);//a的数量大于一半时n/2的位置上必然是a
        return max(2 * count - n,ans);//如果a的数量小于一半那么第一个小于零 
    }
};