首页 > 代码库 > set

set

2024-11-19 16:14:39   203人阅读

  Description
　　对于给出的一串数字，求出该串中最长的连续并且每个数仅出现一次的子序列。
　　
　 Input
  1
  5
  1
  2
  3
  2
  1
 
 Output
  3
 
　 由于数据范围很大 0~1e9，查找到一个数遍历一遍1e9不现实，这样就需要一种快速识别这个数是否出现过的方法。
  就学习了一下set这个容器。
 
　 定义好set< > s; <>里面为容器的类型。
　 s.count();查找这个元素出现的次数。
　 s.insert( )在容器中插入一个元素。
　 s.erase( )删除容器当前的这个元素。

　 s.begin( ) 返回set容器的第一个元素。

　 s.end( ) 返回set容器的最后一个元素。

　 s.clear( ) 删除set容器中的所有的元素。

　 s.empty( ) 判断set容器是否为空。

  s.size( ) 当前set容器中的元素个数。
　
　 对于set<int> s;的过程相当于把容器清空了一遍，因为这点wa了两次，写在循环中就通过了，也可以用s.clear()来删除。
　　 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int a[maxn];

int main(){
	int T,n,L,R,ans;
	scanf("%d",&T);
	while(T--){
		set<int> s;
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		sort(a,a+n);
		L = R = ans = 0;
		while(R<n){
			while(R<n && !s.count(a[R])){
				s.insert(a[R]);
				R++;
			}
			ans=max(ans,R-L);
			s.erase(a[L]);
			L++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

 

 

set


联系
我们