`

【串和序列处理 8】最长平台问题

阅读更多

1、经典最长平台算法

 

已知一个已经从小到大排序的数组,这个数组中的一个平台(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) 程序语句也要越少越好。
这个问题曾经困扰过David Gries 这位知名的计算机科学家。本题与解答取自David Gries 编写的有关程序设计的专著。

#include  <stdio.h>
int longest_plateau()
{
     int  x[] = { 3, 4, 4, 7, 8, 9, 9, 9, 9, 10};
     int  n   = sizeof(x)/sizeof(int);
     int  length = 1;         /* plateau length >= 1.     */
     int  i;

     for (i = 1; i < n; i++)
          if (x[i] == x[i-length])
               length++;
     return length;
}

这是一个时间复杂度为O(n) 的经典算法,其代码十分简练。

 

另外,我自己也写了一个时间复杂度为O(n)的算法,原理就是找出所有平台分界位置,后一个位置减前一个位置(平台长度)的最大值。

int longest_plateau(){
	int  keys[] = {3, 4, 4, 7, 8, 9, 9, 9, 9, 10};
	int  size = sizeof(keys)/sizeof(int);

	int maxLength=0; //记录最大的平台长度
	int maxLowBound=-1; //记录最大平台的首偏移
	int maxHighBound=-1; //记录最大平台的尾偏移

	int index=1; // 两个分界点位置进行一次比较,index=0或1
	int bound[2]; //记录每一次比较长度的首,尾偏移

	bound[0]=1;//第一个平台的首偏移在数组第0个位置
	for(int i=1;i<size;i++){

		if(keys[i]!=keys[i-1]){
			bound[index++]=i; //当前平台的尾偏移(即下一个平台的首偏移)
		}

		if(index==2){ //比较平台长度
			if(bound[1]-bound[0]>maxLength){
				maxLength=bound[1]-bound[0];
				maxLowBound=bound[0];
				maxHighBound=bound[1];
			}
			bound[0]=bound[1]; //当前平台的尾偏移成为下一个平台的首偏移
			index=1; //准备记录下一个平台的尾偏移到Bound[1]上
		}
	}

//	printf("longest plat's length is %d\n",maxLength);
//	printf("longest plat is ");
//	for(int j=maxLowBound;j<maxHighBound;j++){
//		printf("%d",keys[j]);
//	}

	return maxLength;
}

 

2、改进的最长平台算法

 

上面O(n)的时间复杂度级别已经很不错了,但是如果n值特别大,那么仍然要比较n次才可以出结果,我们能不能降低比较次数呢? 显然,这个问题是可以优化的。

 

我们再来回顾一下David Gries的经典算法(代码1的line: 9),不管当前最长平台的长度为多少,每一次比较都是i++。难道每一次比较都是必须的吗? 比如下面这个平台串:

                                              pArr[]:    1  1  1  2  2  2  2   2  3  3    4   4    5    5

                                              index:     0  1  2  3  4  5  6  7  8   9  10  11  12  13

分析: 当pArr[2]==pArr[0]的时候,最长平台长度已经增到了3。此时继续比较pArr[3]==pArr[0]发现不相等。那么说明pArr[3]已经开始了一个新的平台。依据经典算法,我们还要继续比较pArr[4]==pArr[1],pArr[5]==pArr[2]。显然,这两个比较是不必要的,因为pArr[3]开始了新的平台,位置3之前的所有数据都不会和3之后的所有数据相等了。

 

根据上面的分析,我们很容易的想到可以跳跃一定的次数进行比较,跳跃多少呢?最简单的想法就是跳跃一个当前的longest(最长平台长度)。因为如果当前pArr[index]==pArr[index+longest]的话,说明当前平台长度比上一次的longest还要长,如果pArr[index]!=pArr[index+longest]的话,那么目前的平台长度绝对不会超过longest,也就没有必要再去比较小于longest的平台长度是多少了。

 

问题并没有想象的那么简单,跳跃longest长度之后,为了下一次还能够跳跃longest长度,有的时候是需要回溯一段距离的。 我们来看看下面的详细算法分析。

 

还是上面的例子,我们来一步一步的研究这个改进的算法。

(1)  首先计算第一个平台 "1  1  1" 得到了当前最长平台长度为longest=3,当前串位置index=3。

(2)  这时我们比较pArr[index]==pArr[index+longest](即比较pArr[3]<->pArr[6])。显然相等,那么longest++(即longest=4)。然后继续循环比较pArr[index]==pArr[index+longest],直到不相等为止。此时index=8, longest=5.

(3)  这一步非常重要,当前的index=8已近开始了一个新的平台, 而当前的longest=5。继续比较pArr[index]==pArr[index+longest](即比较pArr[8]<->pArr[13]),发现不相等。此时我们能不能继续从pArr[13]开始向后跳跃longest=5的长度呢。显然不对,因为pArr[13]并不是平台5的开始位置,pArr[12]=5。如果跳跃longest长度,后面的计算结果将全部错误。 此时,我们必须从13开始回头遍历,直到找到平台的其实位置pArr[12],然后从12位置开始跳跃longest=5的长度才可以。

 

//跳跃最长平台算法
int jump_longest_plateau(int * pArr, int size){
	int longest=1; //最长平台长度
	int index=1;  //平台串位置索引
	//计算第一个平台的长度
	for(;index<size&&pArr[index]==pArr[index-1];index++,count++)
		++longest;
	//跳跃longest比较平台长度
	while((index+longest)<size){
        // 如果跳跃之后相等,则循环继续增大最长平台的长度
		if(pArr[index]==pArr[index+longest]){
			while(pArr[index]==pArr[index+longest]){
				++longest;
			}
			index+=longest;
		}else{ //如果跳跃之后不相等,则回溯寻找当前平台的起始位置
			index+=longest;
			for(;pArr[index]==pArr[index-1];index--);
		}
	}
	return longest;
}

 

算法分析:时间复杂度仍然是O(n)级别 (注意:不要看到双重循环就认为是O(n^2)级别)。随然有的时候需要回溯到平台的起始位置,但改进之后的算法仍然降低了比较次数。 因为跳跃longest后最多需要回溯longest-1次(此时共比较longest次)。也就是最差情况下位置index每次跳跃之后都会回溯到index+1的位置上,因此最差情况下改进算法会蜕化成经典算法的比较次数n。

 

我们列举出一个最差情况的平台串:  1  1  2  2  3  3  4  4  5  5  6  6  7  7 ....

 

平均而言,1000个长度的随机初始化平台串,改进算法的比较次数在149次左右。而经典算法必须比较1000次。

 

 

 

2
0
分享到:
评论

相关推荐

    求字符串的最长平台

    标题中的“求字符串的最长平台”实际上是指寻找一个数组中具有相同值的连续子序列的最大长度,这在数据结构和算法领域中是一个常见的问题。在C语言编程中,这个问题可以通过遍历数组并比较相邻元素来解决。从给出的...

    求字符串的最长公共子序列

    总结来说,最长公共子序列问题是字符串处理中的经典问题,递归方法是理解问题的一种有效途径,但在实际应用中,动态规划通常能提供更好的性能。理解并掌握这种算法有助于提升在相关领域的编程能力。

    C++求最长公共子序列

    1. **引入必要的库**:`#include&lt;iostream&gt;` 和 `#include&lt;string&gt;` 用于输入/输出和字符串处理。 2. **命名空间使用声明**:`using namespace std;` 使代码可以不使用std::前缀调用标准库函数。 3. **常量定义**:`...

    最长公共子序列

    最长公共子序列问题是字符串处理中的经典问题之一,其应用广泛,不仅限于文本编辑和生物信息学,在数据挖掘、机器学习等领域也有其独特的价值。掌握LCS算法的原理与实现,对于提升编程能力和理解数据结构有重要意义...

    最长上升子序列

    这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入...

    C++实现最长公共子序列问题

    最长公共子序列问题是计算机科学中一个经典的算法问题,主要应用于生物信息学、自然语言处理等领域。给定两个字符串`X = x1x2...xm`和`Y = y1y2...yn`,它们的一个共同子序列是同时为两个序列的子序列的任意序列。...

    最长公共子序列MFC实现

    最长公共子序列(Longest Common Subsequence,LCS)是一个经典的计算机科学问题,它涉及到序列比对和字符串处理。在两个或多个序列中,LCS是指没有改变原有顺序的情况下,存在于所有序列中的最长子序列。这个问题在...

    OJ_在字符串中找出连续最长的数字串

    在编程竞赛(OJ)中,"在字符串中找出连续最长的数字串"是一道典型的字符串处理问题。它要求我们从一个给定的字符串中找到最长的一段连续的数字序列。这个问题涉及到字符串遍历、字符判断以及动态规划或滑动窗口等...

    最长公共子序列求解问题

    最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串处理问题,广泛应用于数据挖掘、文本比较、生物信息学等领域。它指的是在不考虑字符顺序的情况下,两个或多个字符串共有的最长的...

    最长公共子序列问题

    最长公共子序列(Longest Common Subsequence,LCS)问题是计算机科学中一个经典的字符串处理问题,主要涉及到动态规划算法的应用。在这个问题中,目标是找到两个序列的最长子序列,这个子序列不必连续,但必须在原...

    在字符串中找出连续最长的数字串+

    "在字符串中找出连续最长的数字串并输出最长的字符串长度"这个问题是字符串处理中的一个经典实例,它涉及到字符串遍历、模式匹配和动态规划等概念。 首先,我们需要理解问题的核心:在给定的字符串中寻找连续的数字...

    求两个字符串的最长公共子序列.pdf

    本文将详细介绍最长公共子序列(Longest Common Subsequence,LCS)算法的概念、原理和实现。LCS 是一种经典的字符串处理算法,广泛应用于自然语言处理、数据压缩、生物信息学等领域。 什么是最长公共子序列? ...

    最长公共子序列算法总结

    最长公共子序列问题是指在给定的两个序列中找出最长的公共子序列。这里的子序列不要求在原序列中连续出现,但必须保持原序列中的相对顺序。例如,序列“ABCD”和“ACDF”的最长公共子序列是“ACD”。 **O(n^2)算法...

    最长公共子序列程序和实验报告

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的字符串问题,广泛应用于文本比较、生物信息学等领域。本实验报告主要围绕LCS算法的实现及其实验过程进行深入探讨。 首先,我们要...

    最长公共子序列问题 C++实现

    最长公共子序列(Longest Common Subsequence,LCS)问题是一个经典的计算机科学问题,主要涉及到字符串处理和动态规划。在两个或多个字符串中找到的最长的子序列,它不一定是连续的,但在这个子序列中,每个字符都...

    最长公共子序列算法C#实现

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要应用于比较和分析两个或多个序列的相似性。在这个问题中,目标是找到两个序列的最长子序列,这个子序列不需要在原序列中...

    最长公共子序列问题.docx

    在这个问题中,给定两个字符串或字符序列A和B,目标是找到这两个序列的最长子序列,这个子序列既在A中也出现在B中,但不必连续。下面我们将深入探讨如何使用动态规划法来解决这个问题。 首先,我们需要理解字符序列...

    输出最长公共子序列 c语言

    根据给定的文件信息,我们可以总结出以下关于“输出最长...综上所述,本程序提供了一种有效的解决方案来求解最长公共子序列问题,通过动态规划的思想和具体实现步骤,可以高效地找到两个字符串之间的最长公共子序列。

    最长公共子序列(c语言)

    最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串问题,主要应用于比较和分析两个或多个序列的相似性。在文本编辑、生物信息学以及版本控制等领域都有广泛应用。C语言是一种广泛...

Global site tag (gtag.js) - Google Analytics