连续子数组长度
一、问题描述
求一个数组A中连续相同数字的和等于s的最长子数组长度
例如A={1,1,2,1,1,1,2,1},s=3,最终返回3
要求算法时间复杂度不超过On),空间复杂度不超过O(1)
二、算法思路
快慢指针:可以设计一个快指针f,一个慢指针s,遍历过程中,如果f.value==s.value,则f++,同时记录一个长度count++,count初值为0,当f.value != s.value时让s=f,同时计算mlength=max(count,mlenght),然后更新count=0;
三、代码
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 int main(){ 5 int n; 6 scanf("%d",&n); 7 int A[n]; 8 for(int i=0;i<n;i++){ 9 scanf("%d",&A[i]); 10 } 11 //以上为测试用例的构造,不计入时间复杂度 12 int mlenght=0,count=0,f=0,s=0; 13 while(f<n){ 14 if(A[f]==A[s]){ 15 f++; 16 count++; 17 }else{ 18 s=f; 19 mlenght = max(count,mlenght); 20 count = 0; 21 } 22 } 23 mlenght = max(count,mlenght); 24 printf("%d",mlenght); 25 return 0; 26 }
四、扩充
2018清华912
问题描述:单峰向量定义为A[0,n)其中前缀{a0,a1,a2……ak}严格递增,后缀{ak+1……an-1}严格递减
请设计一个时间复杂度为O(logn)的算法找出最大值所在位置k
证明算法正确性
证明即使在最坏的情况下算法的时间复杂度也不会超过O(logn)
提示:看到logn,应该第一时间想到二叉树的高度,而与二叉树类似的是折半查找算法,而证明过程可以尝试使用查找次数来证明