题目描述：
给你一个下标从 0 开始的 非递减 整数数组 nums 。
你可以执行以下操作任意次：
- 选择 两个 下标
i 和 j ，满足 i < j 且 nums[i] < nums[j] 。 - 将
nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。
请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。
数据范围：
$1 \le nums.len \le 10^5$
非递减数组
题解：
这类似美团笔试的题目，但是美团那个数据比较垃圾， $n/2$ 都能过。
注意 $1,1,2,2,3,3$ 可以循环删除，这是比较坑的点。因此就不能用大根堆，每次pop两个最大的，大的删去小的，重新push回去了。
考虑贪心，可以使用大根堆，每次pop两个，都减去1，然后重新加回去，也能通过该题。但是复杂度比较高。
首先统计频率，如果频率最高的那个 $cnt$ 超过了一半，说明其他的都可以被他消除，因此答案就是 $cnt - (n - cnt)$ 。如果没有超过一半，说明至少有3组，并且它们的频率都是没有超过一半。那么可以选择最多的那个和另外两个进行消除。
假设三组频率是 $a,b,c$ ，并且 $a >= b >= c$ ， $a + b + c = n; a,b,c \lt \frac{n}{2}$ . 并且 $b + c\gt \frac{n}{2} \gt a$
因为 $a < b + c, b - c < a$ 那么可以先使用 $b,c$ 相互消除，每次减去 $2$ ，直到和 $a$ 最接近，然后使用 $a$ 进行消除。因为 $b-c < a$ 所以肯定能消除到与 $a$ 相等或者与 $a$ 相差 $1$ 。这时使用 $a$ 与 $b,c$ 消除就能得到最优解 $0$ 或 $1$ 。
因此如果最大的频率超过了 $\frac{n}{2}$ 那么最优解就是 $2\times cnt - n$ ；否则答案就是 $n \mod 1$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minLengthAfterRemovals(vector<int> &nums)
{
int n = nums.size();
unordered_map<int, int> mp;
int size = 0;
vector<int> a;
for (int i = 0; i < n; ++i)
{
if (!mp.count(nums[i]))
a.emplace_back(nums[i]);
mp[nums[i]]++;
}
priority_queue<int> q;
for (auto &x : a)
q.push(mp[x]);
while (q.size() > 1)
{
int first = q.top();
q.pop();
int second = q.top();
q.pop();
if (first > 1)
q.push(first - 1);
if (second > 1)
q.push(second - 1);
}
if(q.size() == 0)
return 0;
return q.top();
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int minLengthAfterRemovals(vector<int>& nums) {
unordered_map<int, int> mp;
int n = nums.size();
int ans = 0;
for(auto& x: nums)
{
mp[x]++;
if(mp[x] > n / 2)
{
ans = max(ans, 2 * mp[x] - n);
}
}
if(ans != 0) return ans;
return n & 1;
}
};
|