经典算法——最长平台有关问题

经典算法——最长平台问题
经典最长平台算法

已知一个已经从小到大排序的数组，这个数组中的一个平台（Plateau）就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在1，2，2，3，3，3，4，5，5，6中［1］、［2，2］、［3，3，3］、［4］、［5，5］、［6］都是平台。尝试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在上面的例子中3，3，3就是该数组中最长的平台。

要求：
1、使用的变量越少越好。
2、把数组的元素每一个都只查一次就得到结果。
3、程序的语句也要越少约好。

我尝试写了这个问题的解法，程序还有待优化（还有新的想法，先给出比较直观的解法）

import java.lang.*;public class LargestPlateau{        public static void getLargestPlateau(int[] numberSequence){                int cnt=1;                int index=0;                int largestTimes=1;                int times=1;                while(cnt<numberSequence.length){                        if(numberSequence[cnt-1]!=numberSequence[cnt]){                                if(largestTimes<times){                                        largestTimes=times;                                        index=cnt-times;                                        times=1;                                }else{                                        times=1;                                }                        }else{                                ++times;                        }                        ++cnt;                }                for(int i=index;i<index+largestTimes;++i){                        System.out.print(numberSequence[i]+" ");                }                System.out.println();        }        public static void main(String[] args){                int[] numberSequence={1,2,2,3,3,3,4,5,5,5,5,5,6};                LargestPlateau.getLargestPlateau(numberSequence);        }}

如果只是需要计算出一串元素的最长平台的长度，那么还可以有以下的解法（参考David Gries编写的相关专著）：

import java.lang.*;public class LargestPlateau1{        public static int getMaxLengthofLargestPlateau(int[] numberSequence){                int size=numberSequence.length;                int length=1;                for(int i=1;i<size;++i){                        if(numberSequence[i]==numberSequence[i-length]){                                length++;                        }                }                return length;          //the length of largest plateau        }        public static void main(String[] args){                int[] numberSequence={1,2,2,3,3,3,4,5,5,5,5,5,6,6};                System.out.println("The length of largest plateau : "+LargestPlateau1.getMaxLengthofLargestPlateau(numberSequence));        }}

查看更多 下一篇