求该问题时间复杂度最小的算法

1248762042

给出项数为 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)

monkey-D

c++有个lower_bound函数（不确定是不是最低复杂度）

1248762042

monkey-D 发表于 2021-9-16 15:32
c++有个lower_bound函数（不确定是不是最低复杂度）

可是这个lower_bound要求数组排序啊

jhq999

{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[n];
f=new int[n];
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[j]>val[i])
                {
                        break;
                }
        }
        if(j==n)
                f[i]=0;
        else
        {
                f[i]=j+1;
        }
}
for (i = 0; i < n; i++)
{
        printf("f(%d)=%d,",i+1,f[i]);
}
delete[] val,f;
    return 0;
}

1248762042

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)的算法

jhq999

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[n];
        f=new int[n];
        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[j]>val[i])
                                {
                                        break;
                                }
                        }
                        if(j==n)
                                f[i]=0;
                        else
                        {
                                m=j;
                                f[i]=j+1;
                        }
                }
                else
                {
                        f[i]=m+1;
                }
        }
        for (i = 0; i < n; i++)
        {
                printf("f(%d)=%d,",i+1,f[i]);
        }
        delete[] val,f;
        return 0;


}

晴雨皆宜

开卷有益，多多益善····