最长平台问题2012年12月24日

问题描述:已知一个已经从小到大排序的数组，这个数组中的一个平台就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在1,2,2,3,3,3,4,5,5,6中1,2.2,3.3.3,4,5.5,6都是平台。编写一个程序，接收一个数组，把这个数组中最长的平台找出来。在上面的例子中3.3.3就是该数组中最长的平台。

我的思路:用distance变量表示平台的长度，从数组target中的第i个数开始，比较target[i]与target[i+distance]，如果相等，就distance++；如果不等，就将i+=distance.这样循环下去，知道i+distance==数组长度为止。这样的算法的时间复杂度是O(n)，而且一般情况只会运行少于n的次数。代码如下:

 1 #include <stdio.h>
 2 #define MAX 1000
 3 
 4 void max_platform(int *target,int len);
 5 
 6 int main()
 7 {
 8     int test[]={1,2,2,3,3,3,4,5,5,6};
 9     int len=sizeof(test)/sizeof(int);    
10     max_platform(test,len);
11     return 0;
12 }
13 
14 void max_platform(int *target,int len)
15 {
16     int distance=1; 
17     int result[MAX]={0};
18     result[0]=1;
19     int i,j;
20     int count=0;
21     for(i=0;i+distance<len; )
22     {
23         count++;
24         if(target[i+distance]==target[i])  
25             result[i]=++distance;
26         else
27             i+=distance;
28     }
29     //打印出最长的平台
30     for(i=0;i<len;i++)
31     {
32         if(result[i]==distance)  
33         {
34             printf("distance: %d\n",distance);
35             for(j=0;j<distance;j++) 
36                 printf("%d ",result[i]);
37             printf("\n");
38         }
39     }
40     printf("\n\ncount:%d\n",count);
41 }

我还在资料上查到另外一种技巧(思路与我的思路很类似):L是平台长度，从第i个数开始，循环比较target[i]与target[i-L]是否相等。如果相等，则L++;如果不等，则继续循环。代码如下:

1 for(int i=1;i<size;i++)  
2 {  
3         if(x[i]==x[i-L])  
4             L++;  
5 }

如果您觉得我的文章对你有帮助，请推荐一下，非常感谢。