题目描述
难度分:1500
输入n(1≤n≤2000)和长为n的数组a(1≤a[i]≤109)。
删除a的一个连续子数组(可以是空的),使得剩余元素互不相同。
输出这个子数组的最短长度。
输入样例1
3
1 2 3
输出样例1
0
输入样例2
4
1 1 2 2
输出样例2
2
输入样例3
5
1 4 1 4 9
输出样例3
2
算法
二分答案
比较容易看出单调性,肯定是删的子数组长度越大,越容易让剩余数字各不相同,因此二分这个最短长度。
对于一个给定的删除长度len,它对应的子数组为[l,r],那么在check的时候我们就需要知道[1,l)和(r,n]中的元素是不是互不相同。可以做一个前后缀分解,维护两个哈希表pre、suf,pre存前缀[1,l)的元素频数,suf存后缀(r,n]的元素频数。
- 如果对于一个长度len,存在一个子数组[l,r]满足pre的大小为l,suf的大小为n−r,且这两个哈希表的key没有交集,就说明可以通过删除[l,r]使得剩余的元素互不相同,返回
true
。记录答案,并往左搜索看长度能不能更小。 - 否则len就太小了,应该往右搜索。
复杂度分析
时间复杂度
二分长度的时间复杂度为O(log2n)。check的时候滑动窗口的时间复杂度是O(n)的,在这个过程中维护pre和suf两个哈希表。检查pre和suf交集是否为空的时间复杂度也是O(n),因为在最差情况下pre和suf中的键值对数量为O(n)级别。
综上,整个算法的时间复杂度为O(n2log2n)。
空间复杂度
空间消耗主要在于pre和suf两个哈希表,在最差情况下一共会存O(n)个键值对,因此额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2001;
int n, a[N];
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
bool check(int len) {
unordered_map<int, int, custom_hash> pre, suf;
for(int i = len + 1; i <= n; i++) {
suf[a[i]]++;
}
if(suf.size() == n - len) return true;
for(int r = len + 1; r <= n; r++) {
suf[a[r]]--;
if(suf[a[r]] == 0) suf.erase(a[r]);
int l = r - len;
pre[a[l]]++;
bool ok = pre.size() == l && suf.size() == n - r;
for(auto&[num, cnt]: pre) {
if(!ok) break;
if(suf.count(num)) {
ok = false;
}
}
if(ok) return ok;
}
return false;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) {
r = mid;
}else {
l = mid + 1;
}
}
printf("%d\n", r);
return 0;
}