two pointers编程思想

什么是two pointers

two pointers是算法编程中一种非常重要的思想，或者说是一种编程技巧。它非常简洁和高效。

• 以一个例子引入：给定一个递增的正整数序列和一个正整数M，求序列中的两个不同位置的数a和b,使得它们的和恰好为M，输出所有满足条件的方案。如给定序列{1,2,3,4,5,6}和正好是M=8，就存在2+6=8与3+5=8成立。

  直观的想法是使用二重循环枚举序列中的a和b，判断和是否为M

  1 2 3 4 5 6 7

  for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(a[i] + a[j] == M){ printf("%d %d\n", a[i], a[j]); } } }

  显然，这种做法时间复杂度为$O(n^2)$，对n在$10^5$的规模时是无法承受的。

  two pointers实现方法：

  1 2 3 4 5 6 7 8 9 10

  while(i < j){ if(a[i] + a[j] == M){ i++; j--; }else if(a[i] + a[j] < M){ i++; }else{ j--; } }

  时间复杂度为O(n)，two pointers思想充分利用了序列递增的性质，以很浅显的思想降低了复杂度。

• 再来看一个序列合并的问题：假如两个非递减序列A和B，要求将它们合并为一个非递减序列C。

  1 2 3 4 5 6 7 8 9 10 11 12 13

  int merge(int A[], int B[], int C[], int n, int m){ //n,m分别为A，B的序列长度 int i = 0, j = 0; index = 0; while(i < n && j < m){ if(A[i] <= B[j]){ C[index++] = A[i++]; }else{ C[index++] = B[j++]; } } while(i < n) C[index++] = A[i++]; while(j < m) C[index++] = B[j++]; return index; }

• Two pointers 利用问题本身与序列的特性，使用两个下标i,j对序列进行扫描（可以同向扫描，也可以反响扫描），以较低的复杂度（一般是O(n)的复杂度）解决问题。

例子B1030/A1085 完美数列： two pointers实现

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤m**p，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：

输入第一行给出两个正整数 N 和 p，其中 N（≤105）是输入的正整数的个数，p（≤109）是给定的参数。第二行给出 N 个正整数，每个数不超过 109。

输出格式：

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：

1
2

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

1

8

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100010;
int n,p,num[maxn];
//two pointers实现
int main(){
    scanf("%d%d",&n,&p);
    for(int i = 0; i < n; i++){
        scanf("%d",&num[i]);
    }
    sort(num, num + n);
    int i = 0, j = 0, count = 1;
    while(i < n && j < n){
        while(j < n && num[j] <= (long long)num[i] * p){
            count = max(count, j - i + 1);
            j++;
        }
        i++;
    }
    printf("%d\n",count);
    return 0;
}

• ← Previous Post
• Next Post →

欢迎访问 chenyawei 的博客, 若有问题或者有好的建议欢迎留言，笔者看到之后会及时回复。 评论点赞需要github账号登录，如果没有账号的话请点击 github 注册， 谢谢 !