class Solution {
public:
int minDeletion(vector<int>& nums) {
}
};
2216. 美化数组的最少删除数
给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length 为偶数i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立注意，空数组同样认为是美丽数组。
你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使 nums 变为美丽数组所需删除的 最少 元素数目。
示例 1：
输入：nums = [1,1,2,3,5] 输出：1 解释：可以删除nums[0]或nums[1]，这样得到的nums= [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。
示例 2：
输入：nums = [1,1,2,2,3,3] 输出：2 解释：可以删除nums[0]和nums[5]，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 105原站题解
javascript 解法, 执行用时: 88 ms, 内存消耗: 50.9 MB, 提交时间: 2023-11-21 19:33:20
/**
* @param {number[]} nums
* @return {number}
*/
var minDeletion = function(nums) {
let ans = 0, n = nums.length, check = true;
for (let i = 0; i + 1 < n; i++) {
if (nums[i] == nums[i + 1] && check) {
ans++;
} else {
check = !check;
}
}
if ((n - ans) % 2 != 0) {
ans++;
}
return ans;
};
cpp 解法, 执行用时: 1088 ms, 内存消耗: 228.8 MB, 提交时间: 2023-06-20 14:52:15
/**
* dp
**/
class Solution {
public:
int minDeletion(vector<int>& nums) {
// 作为第二个数时，最多保留几个数
int ans = 0;
// 作为第一个数时，最多保留几个数
map<int, int> mp;
multiset<int> st;
for (int x : nums) {
// 剔除 x 作为第一个数的情况，以满足第二个数不能与第一个数相同
if (mp.count(x)) st.erase(st.find(mp[x]));
// x 作为第一个数，前一个数任意
mp[x] = max(mp[x], ans + 1);
// x 作为第二个数，前一个数不能是 x，我们已经从 st 里剔除了
if (!st.empty()) ans = max(ans, *(st.rbegin()) + 1);
// 更新 x 作为第一个数的情况
st.insert(mp[x]);
}
return nums.size() - ans;
}
};
cpp 解法, 执行用时: 140 ms, 内存消耗: 118.4 MB, 提交时间: 2023-06-20 14:51:28
/**
* 贪心
* 如果当前数可以作为数对中的第二个数就保留，
* 它的下一个数直接作为下一个数对中的第一个数。
**/
class Solution {
public:
int minDeletion(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for (int i = 0; i + 1 < n; i++) {
if (nums[i] == nums[i + 1]) ans++;
else i++;
}
if ((n - ans) % 2) ans++;
return ans;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 55.3 MB, 提交时间: 2023-06-20 14:50:18
class Solution {
public int minDeletion(int[] nums) {
int l = 0, r = 1, cnt = 0, n = nums.length;
while (r < n) {
if (nums[ l ] != nums[ r ++ ]) {
cnt += r - l - 2;
l = r ++;
}
}
return cnt + ( l < n ? r - l : 0 );
}
}
cpp 解法, 执行用时: 128 ms, 内存消耗: 118.3 MB, 提交时间: 2023-06-20 14:49:30
class Solution {
public:
int minDeletion(vector<int>& nums) {
int l = 0, r = 1, cnt = 0, n = nums.size();
while (r < n) {
if (nums[ l ] != nums[ r ++ ]) {
cnt += r - l - 2;
l = r ++;
}
}
return cnt + ( l < n ? r - l : 0 );
}
};
python3 解法, 执行用时: 120 ms, 内存消耗: 27.6 MB, 提交时间: 2023-06-20 14:47:34
# 双指针，一对对查找
class Solution:
def minDeletion(self, nums: List[int]) -> int:
l, r, cnt, lenn = 0, 1, 0, len(nums)
while r < lenn:
if nums[l] == nums[r]:
r += 1
else:
cnt += r - l - 1
l, r = r + 1, r + 2
if l < lenn: cnt += r - l
return cnt
golang 解法, 执行用时: 196 ms, 内存消耗: 8.6 MB, 提交时间: 2023-06-20 14:46:46
func minDeletion(a []int) (ans int) {
odd := false // 栈大小的奇偶性
for i, n := 0, len(a); i < n; {
start := i
// 注意这里的 i 和外层循环的 i 是同一个变量，因此时间复杂度为 O(n)
for i < n && a[i] == a[start] { i++ }
l := i - start // 连续相同元素个数
if !odd { // 只能放一个元素
ans += l - 1
odd = true
} else if l == 1 {
odd = false
} else { // 放两个元素，奇偶性不变
ans += l - 2
}
}
if odd { // 栈大小必须为偶数
ans++
}
return
}