【uva 11572】Unique Snowflakes（算法效率--滑动窗口，3种实现方法）-白红宇

【uva 11572】Unique Snowflakes（算法效率--滑动窗口，3种实现方法）

阅读量：6816 次

发布时间：2019-06-26

本文共 2178 字，大约阅读时间需要 7 分钟。

题意：求长度为N的序列中，最长的一个无重复元素的连续子序列。

解法：[L,R]每次R++或L++延伸就可以得到答案。

实现：（1）next[],last[]——O(n)；

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define N (int)1e6+10 8  9 struct node{
    int x,d,t;}a[N],b[N];10 int hou[N],last[N];11 int n,m,i,j,k;12 13 bool cmp(node x,node y) {
    return x.x
           
            y?x:y;}15 void input()16 {17 scanf("%d",&n);18 for (i=1;i<=n;i++)19 {20 scanf("%d",&a[i].x);21 a[i].t=i;22 }23 }24 void init()25 {26 memcpy(b,a,sizeof(a));27 sort(b+1,b+1+n,cmp);28 m=1,a[b[1].t].d=m;29 for (i=2;i<=n;i++)30 {31 if (b[i].x!=b[m].x) b[++m]=b[i];32 a[b[i].t].d=m;33 }34 memset(hou,-1,sizeof(hou));35 for (int i=1;i<=n;i++)36 {37 last[i]=hou[a[i].d];38 hou[a[i].d]=i;39 }40 }41 int solve()42 {43 int l=1,r=1,ans=0;44 while (r<=n)45 {46 while (r<=n&&last[r]

Code1

（2）set.insert(),count(),erase()——O(nlogn)；

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn = 1000000 + 5; 6 int A[maxn]; 7 int main( ) { 8 int T, n; 9 scanf("%d", &T);10 while(T--) {11 scanf("%d", &n);12 for(int i = 0; i < n; i++) scanf("%d", &A[i]);13 set
         
           s;14 int L = 0, R = 0, ans = 0;15 while(R < n) {16 while(R < n && !s.count(A[R])) s.insert(A[R++]);17 ans = max(ans, R - L);18 s.erase(A[L++]);}19 printf("%d\n", ans);20 }21 return 0;22 }

Code2（from 紫书）

（3）map.clear(),count()——O(nlogn)。

1 #include
      
        2 #include
        3 using namespace std; 4 const int maxn = 1000000 + 5; 5 int A[maxn], last[maxn]; 6 map
        
          cur; 7 int main( ) { 8 int T, n; 9 scanf("%d", &T);10 while(T——) {11 scanf("%d", &n);12 cur.clear( );13 for(int i = 0; i < n; i++) {14 scanf("%d", &A[i]);15 if(!cur.count(A[i])) last[i] = -1;16 else last[i] = cur[A[i]];17 cur[A[i]] = i;18 }int L = 0, R = 0, ans = 0;19 while(R < n) {20 while(R < n && last[R] < L) R++;21 ans = max(ans, R - L);22 L++;23 } p24 rintf("%d\n", ans);25 } r26 eturn 0;27 }

Code3（from 紫书）

转载于:https://www.cnblogs.com/konjak/p/5977207.html

你可能感兴趣的文章

张裕葡萄酒将现身“中华老字号故宫过大年”展览活动

查看>>

中国集体建设用地建租赁住房试点扩容新增福州等5城

查看>>

湖北长阳：产妇临盆扶贫干部客船上接生（图）

查看>>

朋友圈揽客上门服务浙江一“美容医生”非法行医被刑拘

查看>>

《声临其境》第二季！“铁三角”王刚、张国立、张铁林节目首合体