删除数对后的最小数组长度

题目

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

---

给你一个下标从 0 开始的 非递减 整数数组 nums 。

你可以执行以下操作任意次：

• 选择 两个 下标 i 和 j ，满足 i < j 且 nums[i] < nums[j] 。
• 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

示例 1：

输入：nums = [1,3,4,9]
输出：0
解释：一开始，nums = [1, 3, 4, 9] 。
第一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 1 < 3 。
删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 4 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

示例 2：

输入：nums = [2,3,6,9]
输出：0
解释：一开始，nums = [2, 3, 6, 9] 。
第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 2 < 6 。
删除下标 0 和 2 处的元素，nums 变成 [3, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 3 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

示例 3：

输入：nums = [1,1,2]
输出：1
解释：一开始，nums = [1, 1, 2] 。
第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 1 < 2 。
删除下标 0 和 2 处的元素，nums 变成 [1] 。
无法对数组再执行操作。
所以，可以得到的最小数组长度为 1 。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• nums 是 非递减 数组。

题解

方法一：

思路

贪心

每次可以选择两个不同的元素进行抵消。

我们统计每种元素的频次。

设最大的频次为mx，元素总个数为n，如果mx大于一半的元素，那么不能完全抵消。会剩余mx-(n-mx)=2*mx-n个。

否则如果n是偶数一定能完全抵消，由于mx<=n-mx。我们可以将n-mx中任意选两个不同元素可以进行抵消，那么一定存在一个k，使得n-mx-2*k = mx，注意n是奇数时，会有一个剩余无法抵消。

由于给出的数组是非降序的。如果mx是大于一半的元素，那么nums[n/2]便是频次最高的元素。然后我们可以二分找到第一个大于等于nums[n/2]的位置，以及第一个大于nums[n/2]的位置，两者相减就得到了频次；如果mx不是是大于一半的元素，答案则取决于n的奇偶性。

代码

class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        int n = nums.size();
        int mx = upper_bound(nums.begin(), nums.end(), nums[n/2]) - lower_bound(nums.begin(), nums.end(), nums[n/2]);
        if (mx*2 > n) return 2*mx-n;
        return n%2;
    }
};