2.3.4超时,请教大佬们如何优化代码的时间复杂度
查看原帖
2.3.4超时,请教大佬们如何优化代码的时间复杂度
1314163
bu_chi_suan楼主2024/3/25 18:19

本人只学习了C语言和部分STL的知识,代码如下:

#include<cstdio>
#include<algorithm>
#include<cmath>
int num[200001],cnt=0;
void search(int* p,int n,int q)//二分查找 
{
	int res=0,left=0,right=n-1,mid;
	while(left<=right)
	{
		mid=left+(right-left)/2;
		//优化后直接找出符合条件的元素中的第一个元素下标(res) 
		if(p[mid]>=q)
		{
		    res=mid;
		    right=mid-1;
		}
		else if(p[mid]<q)
		    left=mid+1;
		    
	}
	//从符合条件的第一个元素开始,找出共有几个 
	while(p[res]==q)
	{
		res++;
		cnt++;
	}
	return;
}
int main()
{
	int t,N,C;
	scanf("%d%d",&N,&C);
	for(int i=0;i<N;i++)
	{
		scanf("%d",&num[i]);
	}
	for(int i=0;i<N-1;i++)//对得到的数组从小到大排序 
	{
		for(int j=0;j<N-i-1;j++)
		{
			if(num[j]>=num[j+1])
			{
				t=num[j];
				num[j]=num[j+1];
				num[j+1]=t;
			}
		}
	}
    for(int i=0;i<N;i++)//查找元素(A-B=C的数量,只需查找元素(B+C)有几个即可) 
    {
    	search(num,N,num[i]+C);
	}
    printf("%d",cnt);
	return 0;
}
2024/3/25 18:19
加载中...