求该问题时间复杂度最小的算法
给出项数为 n 的整数数列 {ai}，下标i从1开始。定义函数 f(i)
f(i) 代表数列中第 i个元素之后第一个大于ai的元素的下标，即f(i)=min { j }, aj>ai,i<j<=n
若不存在，则 f(i)=0
试求出 f(1)…f(n)
输入格式
第一行一个正整数
n。
第二行
n个正整数 a1…an
输出格式
一行 n个整数 f(1)…f(n) c++有个lower_bound函数（不确定是不是最低复杂度） monkey-D 发表于 2021-9-16 15:32
c++有个lower_bound函数（不确定是不是最低复杂度）
可是这个lower_bound要求数组排序啊 本帖最后由 jhq999 于 2021-9-16 17:52 编辑
{1,2,0,8,2}
f(1)=2;f(2)=4;f(3)=4;f(4)=0;f(5)=0
我理解的对吗？
#include <stdio.h>
int main()
{
int i=0,j=0,n=0,m=0,*val,*f;
scanf("%d",&n);
getchar();
val=new int;
f=new int;
i=0;
while(i<n)
{
scanf("%d",(val+i));
i++;
}
m=0;
for(i=0;i<n;i++)
{
for (j = i+1; j < n; j++)
{
if (val>val)
{
break;
}
}
if(j==n)
f=0;
else
{
f=j+1;
}
}
for (i = 0; i < n; i++)
{
printf("f(%d)=%d,",i+1,f);
}
delete[] val,f;
return 0;
}
jhq999 发表于 2021-9-16 17:20
{1,2,0,8,2}
f(1)=2;f(2)=4;f(3)=4;f(4)=0;f(5)=0
我理解的对吗？
理解的是对的但就是想找一种时间复杂度 小于 O(n2)的算法 1248762042 发表于 2021-9-16 20:55
理解的是对的但就是想找一种时间复杂度 小于 O(n2)的算法
int main()
{
int i=0,j=0,n=0,m=0,*val,*f;
scanf("%d",&n);
getchar();
val=new int;
f=new int;
i=0;
while(i<n)
{
scanf("%d",(val+i));
i++;
}
m=0;
for(i=0;i<n;i++)
{
if (i>=m)
{
for (j = i+1; j < n; j++)
{
if (val>val)
{
break;
}
}
if(j==n)
f=0;
else
{
m=j;
f=j+1;
}
}
else
{
f=m+1;
}
}
for (i = 0; i < n; i++)
{
printf("f(%d)=%d,",i+1,f);
}
delete[] val,f;
return 0;
}
开卷有益，多多益善····
页:
[1]