408每日算法——连续子数组长度(2016年清华912)

连续子数组长度

一、问题描述

  求一个数组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,应该第一时间想到二叉树的高度,而与二叉树类似的是折半查找算法,而证明过程可以尝试使用查找次数来证明

上一篇:408算法练习——跳跃游戏(贪心算法)


下一篇:408算法练习——加油站(数组)