这样O(n)的算法能过吗?
查看原帖
这样O(n)的算法能过吗?
1390639
URAISK421楼主2024/10/28 08:21

rt

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5; 	
int a[maxn],sum[maxn];
int n;
int ans;
void read()
{
	cin>>n;
	for(int i = 1 ;i<=n;i++)
		cin>>a[i];
}
void sol(){
	sort(a + 1,a + n + 1);
	int cnt = 1;
	int num = 1;
	for(int i = 1 ; i<=n ;i++)
	{
		if(a[i]!=a[i+1])//相邻的两个元素不相等
		{
			sum[cnt] = num;//num是值为某个数的元素的数量
			num = 1;	//num初始化,准备统计下一个值的元素数量
			cnt++;//cnt是记录有多少个不同的数值
			continue;
		}  
		num++;//统计元素数量
	}
	for(int i = 2 ;i<=cnt;i++)
	{
		if(sum[i]<sum[i-1]) sum[i] = sum[i-1];//如果sum[i]比sum[i-1]小那么sum[i]和sum[i-1]操作后仍然有sum[i-1]个数
		else sum[i] = sum[i];//同理,若sum[i]>sum[i-1],操作后仍然有sum[i]个元素;
	}
	ans = sum[cnt];//最后一项自然就是完全操作后的元素数量
}

int main()
{
	read();
	sol();
	cout<<ans;
	return 0;
}
2024/10/28 08:21
加载中...