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

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
我理解的对吗？

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.        int i=0,j=0,n=0,m=0,*val,*f;
   
7. scanf("%d",&n);
   
8. getchar();
   
9. val=new int[n];
   
10. f=new int[n];
    
11. i=0;
    
12. while(i<n)
    
13. {
    
14. scanf("%d",(val+i));
    
15. i++;
    
16. }
    
17. m=0;
    
18. for(i=0;i<n;i++)
    
19. {
    
20.         for (j = i+1; j < n; j++)
    
21.         {
    
22.                 if (val[j]>val[i])
    
23.                 {
    
24.                         break;
    
25.                 }
    
26.         }
    
27.         if(j==n)
    
28.                 f[i]=0;
    
29.         else
    
30.         {
    
31.                 f[i]=j+1;
    
32.         }
    
33. }
    
34. for (i = 0; i < n; i++)
    
35. {
    
36.         printf("f(%d)=%d,",i+1,f[i]);
    
37. }
    
38. delete[] val,f;
    
39.     return 0;
    
40. }
    

复制代码

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

1. int main()
   
2. {
   
3.         int i=0,j=0,n=0,m=0,*val,*f;
   
4.         scanf("%d",&n);
   
5.         getchar();
   
6.         val=new int[n];
   
7.         f=new int[n];
   
8.         i=0;
   
9.         while(i<n)
   
10.         {
    
11.                 scanf("%d",(val+i));
    
12.                 i++;
    
13.         }
    
14.         m=0;
    
15.         for(i=0;i<n;i++)
    
16.         {
    
17.                 if (i>=m)
    
18.                 {
    
19. 
    
20. 
    
21.                         for (j = i+1; j < n; j++)
    
22.                         {
    
23.                                 if (val[j]>val[i])
    
24.                                 {
    
25.                                         break;
    
26.                                 }
    
27.                         }
    
28.                         if(j==n)
    
29.                                 f[i]=0;
    
30.                         else
    
31.                         {
    
32.                                 m=j;
    
33.                                 f[i]=j+1;
    
34.                         }
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                         f[i]=m+1;
    
39.                 }
    
40.         }
    
41.         for (i = 0; i < n; i++)
    
42.         {
    
43.                 printf("f(%d)=%d,",i+1,f[i]);
    
44.         }
    
45.         delete[] val,f;
    
46.         return 0;
    
47. 
    
48. 
    
49. }

复制代码

晴雨皆宜

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