最长平台的新算法

最长平台问题描述如下：

一个从小到大排列的数组，这个数组中的一个平台就是连续的一段值相同的元素。例如：122333445中22，333等都是平台，333为最长平台。

一般常见的算法是一个计算机科学家首先给出的。

	private static int f1(int[] array) {

		if (array == null || array.length == 0)
			return 0;

		int length = 1;

		for (int i = 1; i < array.length; i++) {
			if (array[i] == array[i - length])
				length++;
		}

		return length;
	}

这段代码的确是简洁优雅的，但是在效率上不是很好。

最长平台有一些特点可以利用，从而使得算法的效率更高。
一个分界点元素指该元素和它的前一个元素不相等。
1 从一个分界点开始剩下的元素个数<=length，则可以直接返回。
2 从一个分界点开始找最大平台，没有必要依次顺序查找，直接跳到该（分界点的坐标+length）的元素进行查找。
  如果（分界点的坐标+length）也是一个分界点，则从原来的分界点到新的分界点（分界点的坐标+length）之间的 元素可以丢掉，从新的分界点重新开始查找最长平台。
  如果（分界点的坐标+length）不是一个分界点，则它有可能在一个最长平台中，判断之，然后继续。
这里主要是考虑到当前最长平台的长度，算法考虑该长度可以跳过一些元素进行处理。

	/**
	 * 最长平台更快的算法
	 */
	private static int f2(int[] array) {

		if (array == null || array.length == 0)
			return 0;

		// 下一个要检测的位置,保证array[next]!=array[next-1]。
		int next = 1;

		for (; next < array.length && array[next] == array[0]; next++)
			;

		// 第一个平台的长度,next>=1。
		int length = next;

		while (next < array.length) {

			// 如果剩下的元素个数<=length，则不可能有最长平台了
			if (array.length - next <= length) {
				break;
			}

			// 向前跳跃length+1,到next+length处进行检查，如果array[next+length]!=array[next+length-1],则
			// next - (next+length-1)这段数据可以丢弃.
			if (array[next + length] != array[next + length - 1]) {
				next = next + length;
			} else {
				// 这个相等的值所在的平台的值.
				int value = array[next + length];

				// 这个相等的值所在的平台的最后一个坐标.
				int endIndex = next + length + 1;
				for (; endIndex < array.length && array[endIndex] == value; endIndex++)
					;
				endIndex = endIndex - 1;

				// 向后跳跃length+1,如果相等，则这个平台是最大平台.
				if (array[endIndex - length] == value) {

					int startIndex = endIndex - length - 1;
					for (; array[startIndex] == value; startIndex--)
						;

					// 更新最大平台的值
					length = endIndex - startIndex;
				}

				next = endIndex + 1;

			}
		}

		return length;
	}

code是比上一个复杂一些，但是速度有了很大的提高，大约提高60%以上。

还有改进的余地，如果在查找一个平台的最后一个坐标或者第一个坐标，可以用2分查找。

评论

17 楼 hsbcnet 2010-09-01  

zhang_xzhi_xjtu 写道

sdh5724 写道

其实， 我觉得可以用lg(n)的复杂度求解的。 因为这是个有序的数列， 根据信息论原理， 查找他的复杂度就是lg(n).  但是， 我想不出怎么用lg(n)解法。 最简单的优化就是基于递归的解法：  f(x+1) = f(x)+ n   x表示当前最大长度。 这样程序上， 就可以越过之前检查过的长度。

这问题怎么跟求最大子序列这么象呢。 除了有序。。。

这个理论的依据是什么？
你的这个递归式子有问题吧。

如果我们用二分法去划分，直到分区内为同一个数(比较头尾)，然后递归上来，O(n)。
对于划分线两边同值的情况，我们需要向两边寻找它的边界，生成多一个递归分支，这样的动作加起来是lg(n)的平方。
这样甚至比简单的遍历还差。

16 楼 zhang_xzhi_xjtu 2010-05-03  

sdh5724 写道

其实， 我觉得可以用lg(n)的复杂度求解的。 因为这是个有序的数列， 根据信息论原理， 查找他的复杂度就是lg(n).  但是， 我想不出怎么用lg(n)解法。 最简单的优化就是基于递归的解法：  f(x+1) = f(x)+ n   x表示当前最大长度。 这样程序上， 就可以越过之前检查过的长度。

这问题怎么跟求最大子序列这么象呢。 除了有序。。。

这个理论的依据是什么？
你的这个递归式子有问题吧。

15 楼 sdh5724 2010-05-02  

其实， 我觉得可以用lg(n)的复杂度求解的。 因为这是个有序的数列， 根据信息论原理， 查找他的复杂度就是lg(n).  但是， 我想不出怎么用lg(n)解法。 最简单的优化就是基于递归的解法：  f(x+1) = f(x)+ n   x表示当前最大长度。 这样程序上， 就可以越过之前检查过的长度。

这问题怎么跟求最大子序列这么象呢。 除了有序。。。

14 楼 Heart.X.Raid 2010-05-02  

对不起  是我搞错了。程序没有错，效率应该是有改进的，但是有最差情况。

13 楼 zhang_xzhi_xjtu 2010-05-01  

Heart.X.Raid 写道

可是我用1,1,1,2,2,3,3,3,3 这组数据测试你的程序，结果是错误的，显示最大平台长度为3，而不是4(3,3,3,3)。

我运行的结果是4.

12 楼 Heart.X.Raid 2010-05-01  

我知道你程序的意思了，逻辑上应该没有问题。效率上确实有提高，但是应该存在最坏的可能性，我觉得当平台的大小基本正序(从大到小)的时候，效率最高，如果逆序过多，则每次跳跃之后基本上都需要回头向前遍历。则效率会大打折扣

11 楼 Heart.X.Raid 2010-04-30  

可是我用1,1,1,2,2,3,3,3,3 这组数据测试你的程序，结果是错误的，显示最大平台长度为3，而不是4(3,3,3,3)。

10 楼 zhang_xzhi_xjtu 2010-04-29  

Heart.X.Raid 写道

LZ 你的改进党的算法有很大问题：

测试一下这组数据吧：  1,1,1,2,2,3,3,3,3

经典算法确实有一些“比较”次数感觉上是没有必要的，但是不能根据当前的length就认定下一次的平台一定可以越过length的长度不参与比较。

就比如上面的例子，1,1,1说明length=3，你认为后面的平台可以越过3次比较吗，也就是next=4--next=6这三个数都可以丢弃吗，注意你丢弃了2,2,3,  本来4个3的平台你丢掉了一个。

我最开始觉得优化确实可以跳跃，但是后来发现，跳跃多少不是一个简单的问题。这和每个平台最开始的分界点有关。

并没有丢弃2,2,3，跳到的地方，是两个3之间，所以不是分界点，所以会计算改点所在的平台。

9 楼 Heart.X.Raid 2010-04-28  

我也在考虑这个算法的优化问题，但目前还没有想到，我们可以一起来思考。有进展了我们相互通知哈。嘻嘻.... 

另外，交个朋友，我喜欢对算法优化专研的朋友。

8 楼 Heart.X.Raid 2010-04-28  

LZ 你的改进党的算法有很大问题：

测试一下这组数据吧：  1,1,1,2,2,3,3,3,3

经典算法确实有一些“比较”次数感觉上是没有必要的，但是不能根据当前的length就认定下一次的平台一定可以越过length的长度不参与比较。

就比如上面的例子，1,1,1说明length=3，你认为后面的平台可以越过3次比较吗，也就是next=4--next=6这三个数都可以丢弃吗，注意你丢弃了2,2,3,  本来4个3的平台你丢掉了一个。

我最开始觉得优化确实可以跳跃，但是后来发现，跳跃多少不是一个简单的问题。这和每个平台最开始的分界点有关。

7 楼 zhang_xzhi_xjtu 2010-03-01  

空间复杂度原来的算法是很好的。
时间复杂度，新的算法是比较好的。

原有的算法的复杂度是n。这个比较简单的可以看出来，它的过程是一个一个的数去测试。它的缺点是没有利用现有的知识。

新的算法利用了一些现有知识。从而不必比每个元素都进行处理。从而使得算法的效率更高。


可以利用的地方。
一个分界点元素指该元素和它的前一个元素不相等。
1 从一个分界点开始剩下的元素个数<=length，则可以直接返回。
2 从一个分界点开始找最大平台，没有必要依次顺序查找，直接跳到该（分界点的坐标+length）的元素进行查找。
  如果（分界点的坐标+length）也是一个分界点，则从原来的分界点到新的分界点（分界点的坐标+length）之间的 元素可以丢掉，从新的分界点重新开始查找最长平台。
  如果（分界点的坐标+length）不是一个分界点，则它有可能在一个最长平台中，判断之，然后继续。
这里主要是考虑到当前最长平台的长度，算法考虑该长度可以跳过一些元素进行处理。

6 楼 newko 2010-03-01  

楼主，能不能说说为什么你的算法效率高。能解释一下吗？从程序结构上看，空间和时间复杂度都比原来那个的高啊。

5 楼 longtime525 2009-12-07  

是啊，还真不知道有这个算法

4 楼 solonote 2009-12-03  

这个算法还是比较简单的,请问一下什么场景会用到此算法,能否举一二例子

3 楼 Eastsun 2009-10-29  

囧...
这样就简单了：

public static int maxSize(int[] array){
           if(array == null) return 0;
           int size = 0;
           int start = 0;
           while(start + size < array.length){
               start += size;
               int elem = array[start];
               if(array[start - size] != elem){
                   for(;array[start - 1] == elem;start --);
                   continue;
               }
               for(;start < array.length && array[start] == elem;size ++,start ++);
           }
           return size;
       }

2 楼 zhang_xzhi_xjtu 2009-10-29  

Eastsun 写道

zhang_xzhi_xjtu 写道

最长平台问题描述如下：

一个从小到大排列的数组，这个数组中的一个平台就是连续的一段值相同的元素。例如：122333445中22，333等都是平台，333为最长平台。

一般常见的算法是一个计算机科学家首先给出的。

	private static int f1(int[] array) {

		if (array == null || array.length == 0)
			return 0;

		int length = 1;

		for (int i = 1; i < array.length; i++) {
			if (array[i] == array[i - length])
				length++;
		}

		return length;
	}

这段代码的确是简洁优雅的，但是在效率上不是很好。

这个代码简洁是简洁，但是错的....
f1(new int[]{1,1,2,3,2}) == 3

一个从小到大排列的数组

1 楼 Eastsun 2009-10-29  

zhang_xzhi_xjtu 写道

最长平台问题描述如下：

一个从小到大排列的数组，这个数组中的一个平台就是连续的一段值相同的元素。例如：122333445中22，333等都是平台，333为最长平台。

一般常见的算法是一个计算机科学家首先给出的。

	private static int f1(int[] array) {

		if (array == null || array.length == 0)
			return 0;

		int length = 1;

		for (int i = 1; i < array.length; i++) {
			if (array[i] == array[i - length])
				length++;
		}

		return length;
	}

这段代码的确是简洁优雅的，但是在效率上不是很好。

这个代码简洁是简洁，但是错的....
f1(new int[]{1,1,2,3,2}) == 3