题目描述
给你一个下标从 0 开始的 非递减 整数数组 nums
。
你可以执行以下操作任意次:
- 选择 两个 下标
i
和j
,满足i < j
且nums[i] < nums[j]
。 - 将
nums
中下标在i
和j
处的元素删除。剩余元素按照原来的顺序组成新的数组,下标也重新从 0 开始编号。
请你返回一个整数,表示执行以上操作任意次后(可以执行 0 次),nums
数组的 最小 数组长度。
样例
输入: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。
输入: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。
输入: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
是 非递减 数组。
算法1
(思维题) $O(n)$
- 求出数组中出现次数最多数字的出现次数,记为 $ma$。
- 如果 $ma$ 超过了数组长度的一半,则必定会有数字剩余,剩余的数字个数为 $ma - (n - ma)$。
- 否则,如果数组长度为奇数,则最后会剩一个,否则可以全部删除。
时间复杂度
- 遍历数组一次,找出众数。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minLengthAfterRemovals(vector<int>& nums) {
const int n = nums.size();
int ma = 0;
for (int i = 1, cnt = 1; i <= n; i++) {
if (i < n && nums[i] == nums[i - 1]) {
++cnt;
} else {
ma = max(ma, cnt);
cnt = 1;
}
}
return max(2 * ma - n, n & 1);
}
};
算法2
(思维题,二分) $O(\log n)$
- 在算法 1 的基础上,可以通过二分的方式判定数组中是否存在出现次数大于一半的数字。
- 找到有序数组的中位数 $x = nums[n / 2]$,并通过
lower_bound
和upper_bound
求出其出现次数。 - 如果 $x$ 是出现次数大于一半的数字,则这个次数就是算法 1 中的 $ma$。
时间复杂度
- 两次二分查询,时间复杂度为 $O(\log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minLengthAfterRemovals(vector<int>& nums) {
const int n = nums.size();
int x = nums[n / 2];
int ma = upper_bound(nums.begin(), nums.end(), x) -
lower_bound(nums.begin(), nums.end(), x);
return max(2 * ma - n, n & 1);
}
};