UVA11527UniqueSnowflakes(滑动窗口+set判重||map)

时间:2017-01-11  |  来源:cnphp6

题意:输入长度为n的序列a,找到一个尽量长的连续子序列a[l] - a[r],使该序列中没有相同的元素

紫薯P239

序列元素从0开始编号,l 和 r 分别表示子序列左右端点,初始化为0,固定 l,判断加入 a[r] 是否重复,如不重复,加入,同时r++,若重复,l++,然后再判断加入a[r]是否重复..

时间复杂度:r从0到n,判重由set来处理lgn,总O(nlgn)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <set>
 5 using namespace std;
 6 int main()
 7 {
 8     int t, n;
 9     scanf("%d", &t);
10     while (t--)
11     {
12         scanf("%d", &n);
13         int *a = new int[n]; //动态分配
14         for (int i = 0; i < n; i++)
15             scanf("%d", &a[i]);
16         int l, r, maxL;
17         maxL = l = r = 0;
18         set<int> s;
19         while (r < n)
20         {
21             while (r < n && s.count(a[r]) == 0)  //判断加入r是否重复
22             {
23                 s.insert(a[r]);
24                 r++;
25             }
26             maxL = max(maxL, r - l);
27             s.erase(a[l]); // 将l处的移除set
28             l++;
29         }
30         printf("%d\n", maxL);
31     }
32     return 0;
33 }
View Code

 

 用map来求

last[i] = x表示第i各位置的数上一次出现是在第x位置,故对于 r 位置的数来说,如果他上次出现在 l 位置之前,则 r 是可以扩展的,否则 l++;

记录每个位置上一次出现的位置可以用map来映射。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int *a = new int[n];
        int *last = new int[n];
        map<int, int> m;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            if ( m.count(a[i]) == 0 )
            {
                last[i] = -1; // 如果上次没有出现,设为-1
            }
            else
            {
                last[i] = m[ a[i] ]; // 如果上次出现,找到上次出现的位置
            }
            m[ a[i] ] = i;  // 这次出现的位置
        }
        int l, r, maxL;
        l = r = maxL = 0;
        while (r < n)
        {
            while (r < n && last[r] < l) // 一定是last[r] < l时,r才加一
                r++;
            maxL = max(maxL, r - l);
            l++;
        }
        printf("%d\n", maxL);
        delete[] a;
        delete[] last;
    }
    return 0;
}