双指针-two pointers

发布于 2020-02-21  88 次阅读


简单介绍

概念: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然后进行输出。

  1. 如果此时已经找到一个A[i]+A[j]=M,想要继续分析找到合适的i和j,下一步应该如何选择才能更加的高效,显然可以从给出的背景条件来看,由A序列是个递增序列可以知道,如果在找到的上述A[i]+A[j]=M条件下将i单独后移显然结果大于c的,而将j前移显然后来的结果都是小于c的,所以下一个查找区间应该[i+1,j-1]开始。

  2. 如果找到的A[i]+A[j]>M,因此不等式a[i+1]+a[j]>M成立,显然此时如果将i后移这个结果只会继续增加,偏离了正确的结果,所以下一个查找区间应该只会在[i,j-1]内。

  3. 如果找到的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的应用场景

  • 序列合并问题
  • 归并排序
  • 快速排序

参考

two pointers、归并排序、快速排序问题

本文标题:《双指针-two pointers》

本文链接:https://wnag.com.cn/902.html

特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~


正因为有要好好实现的梦想,所以今天也要好好加油。