问题:已知一个从小到大的有序数组,这个数组中一个平台就是连续的一串
值相同的数,并且不可再延伸。请找出最长的平台。例如:1,2,2,3,3,3,3,4,5,5,6中
1,2,3,4,5,6各自是一个平台,找出连续最长的。
先上python,本人思考问题后总是先用python实现,然后再转成c或者c++,
难道python实现起来容易?我感觉有点。
plateau.py :
1 def num(a):
2 t=a[0]
3 c=0
4 b=0
5 tmp=0
6 for i in a:
7 if t==i:
8 c+=1
9 else:
10 if b<c:
11 tmp=t
12 b=c
13 t=i
14 c=1
15 if b<c:
16 tmp=a[len(a)-1]
17 #b=c
18 return tmp
19 if __name__=='__main__':
20 a=[1,1,1,1,1,1,1,1,1,2,2,3,3,3,\
21 3,4,5,5,5,6,6,6,6,6,6,7,7,8,8,8,8,8,8,8,8,8,8]
22 print num(a)
c语言实现,plateau.c:
1 #include <stdio.h>
2 int num(int *a,int len)
3 {
4 int t=a[0];
5 int c=0,b=0,tmp=0;
6 for (int i =0;i<len;i++)
7 {
8 if(t==a[i])
9 c++;
10 else{
11 if(b<c){
12 tmp=t;
13 b=c;
14 }
15 t=a[i];
16 c=1;
17
18 }
19 }
20 if(b<c)
21 tmp=a[len-1];
22 return tmp;
23 }
24 int main()
25 {
26 int arr[]={1,1,1,1,1,1,1,1,1,2,2,3,3,3,3,4,5,5,5,6,6,6,6,6,6,7,7,8,8,8,8,8,8,8,8,8,8};
27 int tmp=num(arr,37);
28 printf("%d\n", tmp);
29 return 0;
30 }
程序跑起来后,感兴趣看看python程序与c的时间比较:
1 $ time python plateau.py
2 8
3
4 real 0m0.144s
5 user 0m0.015s
6 sys 0m0.109s
7
8
9 $ time ./plateau //gcc -o plateau plateau.c
10 8
11
12 real 0m0.046s
13 user 0m0.000s
14 sys 0m0.030s
主要看红色两行与绿色两行分别相加的结果来比较,C程序可不是一般的快。
至于real时间主要是操作系统中存在中断,导致同一个程序运行时间差异可能也很大,
所以用real比较不太准确,上面的时间计算相对精确些。最近看算法,记录记录,要的要的。
但是上面的程序效率不高,但是优点是能够很容易的知道哪个数连续最长。下面介绍一个
非常高效的计算出最长数连续多长,但是是哪个数最长,不好解决。主要思想是如果一个数n连续的
长度L,那么下一个比n长就自加L,否则L不变,继续下一个数。
simple.c :
1 #include <stdio.h>
2 int num(int *a,int length)
3 {
4 int len=1;
5 int i;
6 for(i=1;i<length;i++)
7 if(a[i]==a[i-len])
8 len++;
9 return len;
10 }
11 int main()
12 {
13 int arr[]={1,1,1,1,1,1,1,1,1,2,2,3,3,3,3,4,5,5,5,6,6,6,6,6,6,7,7,8,8,8,8,8,8,8,8,8,8};
14 int tmp=num(arr,37);
15 printf("%d\n", tmp);
16 return 0;
17 }
原文链接: https://www.cnblogs.com/wuchaofan/archive/2013/06/08/3127682.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/91660
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!