我遇到了一个问题,要求程序计算一个区间内的点数。本题提供了大量未排序的点,且lo,hi(限制lo<=hi),目的是枚举[lo,hi]内的点。问题是虽然我的代码是正确的,但是在给定的时间(2200ms)内完成太耗时了。我的代码可以在 O(n) 内完成这个任务。请问有没有更快的方法。
int n,m,c,lo,hi;
cin>>n>>m;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cin>>lo>>hi;
c=0;
for(int j=0;j<n;j++){
if(arr[j]<=hi&&lo<=arr[j])c++;
}
cout<<c<<endl;
最佳答案
不可能在 O(n)
时间内解决这个问题,因为您必须至少考虑所有输入一次。
但是,您可以减少 n
的常数因子——您是否考虑存储一组 (start, end)
间隔,而不是一个简单的数组?导致速度变慢的输入大小是多少?
编辑:经过进一步测试,瓶颈似乎实际上是使用 cin
读取数字。
尝试将 cin >> x;
的每个实例替换为 scanf("%d", &x);
— 对我来说,这将运行时间降低到大约 0.08秒。
关于c++ - 计算线间隔中的点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34647051/