class Solution {
public:
int minLengthAfterRemovals(vector<int>& nums) {
}
};
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 <= 1051 <= nums[i] <= 109nums 是 非递减 数组。原站题解
javascript 解法, 执行用时: 100 ms, 内存消耗: 52.1 MB, 提交时间: 2023-09-17 22:44:40
/**
* @param {number[]} nums
* @return {number}
*/
var minLengthAfterRemovals = function (nums) {
const n = nums.length;
const x = nums[n >> 1];
const maxCnt = lowerBound(nums, x + 1) - lowerBound(nums, x);
return Math.max(maxCnt * 2 - n, n % 2);
};
var lowerBound = function (nums, target) {
let left = -1, right = nums.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
const mid = left + ((right - left) >> 1);
if (nums[mid] < target)
left = mid; // 范围缩小到 (mid, right)
else
right = mid; // 范围缩小到 (left, mid)
}
return right; // 或者 left+1
}
golang 解法, 执行用时: 152 ms, 内存消耗: 7.9 MB, 提交时间: 2023-09-17 22:44:23
func minLengthAfterRemovals(nums []int) int {
n := len(nums)
x := nums[n/2]
maxCnt := sort.SearchInts(nums, x+1) - sort.SearchInts(nums, x)
return max(maxCnt*2-n, n%2)
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 140 ms, 内存消耗: 145.7 MB, 提交时间: 2023-09-17 22:44:10
class Solution {
public:
int minLengthAfterRemovals(vector<int> &nums) {
int n = nums.size();
int x = nums[n / 2];
int max_cnt = upper_bound(nums.begin(), nums.end(), x) -
lower_bound(nums.begin(), nums.end(), x);
return max(max_cnt * 2 - n, n % 2);
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 57.1 MB, 提交时间: 2023-09-17 22:43:59
class Solution {
public int minLengthAfterRemovals(List<Integer> nums) {
int n = nums.size();
int x = nums.get(n / 2);
int maxCnt = lowerBound(nums, x + 1) - lowerBound(nums, x);
return Math.max(maxCnt * 2 - n, n % 2);
}
// 开区间写法
private int lowerBound(List<Integer> nums, int target) {
int left = -1, right = nums.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums.get(mid) < target)
left = mid; // 范围缩小到 (mid, right)
else
right = mid; // 范围缩小到 (left, mid)
}
return right; // 或者 left+1
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 25.5 MB, 提交时间: 2023-09-17 22:43:42
class Solution:
def minLengthAfterRemovals(self, nums: List[int]) -> int:
n = len(nums)
x = nums[n // 2]
max_cnt = bisect_right(nums, x) - bisect_left(nums, x)
return max(max_cnt * 2 - n, n % 2)
def minLengthAfterRemovals2(self, nums: List[int]) -> int:
n = len(nums)
v = max(Counter(nums).values())
return n % 2 if v * 2 <= n else n - (n - v) * 2