简单介绍
概念:two pointers广义上概念就是利用问题本身与序列的特性,利用下标i、j对序列进行扫描,以较低的复杂度来解决问题,其实也不太像是一种算法,说来可以看做是一种编程技巧,一种思想比较适合。
例如在一个递增序列中找到a+b=c的数然后输出a,b的值,M是我们自己指定的数,常规做法很容易想到,两个下标遍历序列做个二重循环就可以解决问题,时间复杂度为o(n^2)。
高复杂度的原因:
(1)对于一个确定的a[i]来说,若当前的a[j]满足a[i]+a[j]>M,显然也有a[i]+a[j+1]>M成立(序列递增),因此不需要对a[j]后进行枚举。如果无视,会造成j的无效枚举。
(2)对于某个a[i]来说,若当前的a[j]满足a[i]+a[j]>M,显然也有a[i+1]+a[j]>M成立(序列递增),因此不需要对a[j]后进行枚举。
但是这个方法是比较烂的,当序列数字较多时(在10^5规模时已经不可承受)时间复杂度会非常的高,程序可行性大打折扣,这时候就要另辟蹊径。
加入现在定义i为A序列首位,j为A序列末位,两下标往中间移动,设计while循环终止条件(i>=j)即可,然后比对是否存在满足条件的i,j然后进行输出。
-
如果此时已经找到一个A[i]+A[j]=M,想要继续分析找到合适的i和j,下一步应该如何选择才能更加的高效,显然可以从给出的背景条件来看,由A序列是个递增序列可以知道,如果在找到的上述A[i]+A[j]=M条件下将i单独后移显然结果大于c的,而将j前移显然后来的结果都是小于c的,所以下一个查找区间应该[i+1,j-1]开始。
-
如果找到的
A[i]+A[j]>M
,因此不等式a[i+1]+a[j]>M成立,显然此时如果将i后移这个结果只会继续增加,偏离了正确的结果,所以下一个查找区间应该只会在[i,j-1]内。 -
如果找到的
A[i]+A[j]<M
,因此不等式a[i]+a[j-1]<M
成立,显然此时如果将j前移这个结果只会继续减少,偏离了正确的结果,所以下一个查找区间应该只会在[i+1,j]内。
说的有点模糊,但请好好分析下,这个思想应该是不太难的,用此方法实现复杂度显然降低不少,此时复杂度为o(n),实现的伪代码如下:
while(i<j)
{
if(a[i]+a[j]==c)
{
printf("%d %d\n", i,j)
i++;
j--;
}
else if(a[i]+a[j]<m)
{
i++;
}
else
{
j--;
}
}
复杂度为o(n)的原因
i初值为0,j初值为n-1,程序仅有i递增、j递减的操作,因此i和k的操作次数最多为n次,因此时间复杂度为O(n)
two pointers的思想
原始的含义就是解决这样的问题
在一个递增序列中找到a+b=c的数然后输出a,b的值,M是我们自己指定的数
而广义上的two pointers利用问题本身与序列的特性,使用i和j两个下标对序列进行扫描(同向方向都可),以较低复杂度解决问题。
two pointers的应用场景
- 序列合并问题
- 归并排序
- 快速排序
参考
版权所有:可定博客 © WNAG.COM.CN
本文标题:《双指针-two pointers》
本文链接:https://wnag.com.cn/902.html
特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~
叨叨几句... NOTHING