双指针算法

前言

听了yxcacwing开的基础算法课的其中一节,听了双指针算法,感觉事实上它还是暴力的做法,但是一分析,它居然是一个O(n)的算法,不禁有点好奇,刚开始是有一点搞不懂,总感觉它还是有两层循环,但是一分析,发现它所有的元素顶多遍历了一遍,两个指针最多也就是走了2n次。感觉有点奇妙,因此写了篇笔记。

双指针算法

我们其实已经接触过双指针算法了,只是我们自己并不知道而已,在哪里接触过呢?没错,再写归并排序的代码的时候以及快速排序的代码的时候。这里,我引用一段归并排序的合并操作 的代码作为例子。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/* 合并操作 */
void merge(int arr[],int l,int mid ,int r){
    int p1=l,p2=mid+1;
    int help[r-l+1],i=0;
    while(p1<=mid && p2<=r){
        help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
    }
    /* 将没导完的数据导到help */
    while(p1<=mid){
        help[i++]=arr[p1++];
    }
    while(p2<=r){
        help[i++]=arr[p2++];
    }
    /* 将help数组拷贝回给arr,注意,合并的是l到r这个区间,并不是0-尽头 */
    for(int k=0;k<i;k++){
        arr[l+k]=help[k];
    }
}

归并排序我们的做法是什么?是不是将数组分成两段,然后分别对这两段进行排序,然后将这两段整合到一个数组中,这个整合的过程就用到了双指针算法,我们看上面的代码,我们两个指针p1p2分别指向排好序的两段,然后我们判断arr[p1]arr[p2]的值的大小,如果说,arr[p1]小的话,那就把arr[p1]填到中间数组,然后p1就往后移,同样的p2也是如此。也就是说,我们用两个指针就可以把两段排好序的数组有序地排到第三个数组当中来,原理就是,谁小谁就装进去,一直装到完为止。这样,我们会发现,对于左半段的数组上的每一个值,p1都只访问了一遍,同样对于右边的数组,p2也只是访问了一遍。也就是说,将两个排好序的数组(设为数组1数组2)整合为一个数组(也要求排好序),假设数组1的长度为a,数组2的长度为b,那么整合操作索要进行的操作数最对为a+b。如果我们用固定某个数组的一个值,然后遍历另一个数组的所有值得做法得话,复杂度是O(a*b),可见,用双指针算法可以达到优化效果。

双指针算法写法

本来我以为双指针算法只有一种写法,那就是y老师教的那种,但是我看了看归并排序那一题,好像那也是一种写法,而且好像更容易理解。这里把两个模板都给出来吧

这是y老师给的模板:

1
2
3
4
5
6
7
8
9
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < b && check(i, j)) j ++ ;

    // 具体问题的逻辑(题目要求干嘛)
}
常见问题分类:
    (1) 对于一个序列,用两个指针维护一段区间
    (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

这里解释一下上面代码的大概意思,就是说,ij都是从0开始,然后如果j所指的东西满足某种性质的话或者他没有到达边界,那j++,用上面归并排序来说明一下:如果arr[p2]<arr[p1],那么我把arr[p2]存入help,然后p2++,如果下一个还满足的话,同样执行这样的操作,一直到arr[p2]>=arr[p1]的时候才停止,这时,执行上面操作的就变成p1了,然后知道数组全部判断完毕。这里我改写一下上面归并排序的代码,以方便理解:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/* 合并操作 */
void merge(int arr[], int l, int mid, int r) {
    int help[r - l + 1], i = 0;
    for (int p1 = l, p2 = mid + 1; p1 <= mid; p1++) {
        while (arr[p2] < arr[p1] && p2 <= r) help[i++] = arr[p2++];
        help[i++] = arr[p1];
    }
    /* 将help数组拷贝回给arr,注意,合并的是l到r这个区间,并不是0-尽头 */
    for (int k = 0; k < i; k++) {
        arr[l + k] = help[k];
    }
}

这是另一种形式:

1
2
3
4
5
6
7
8
9
while(i<=a&&j<=b){
    ······
}
while(i<=a){//处理i没走完的
    ······
}
while(j<=b){
    ······
}

个人感觉这一种比较好理解

以CCF-CSP,202006-2稀疏向量为例

在这篇博客中我用了上面两种解法作为例子。大家可以去那边看一看。

{% post_link CCF-CSP/202006-2稀疏向量 稀疏向量 %}

结束

好了,到这里算是已经写完啦。

0%