two pointers思想 ---- 利用两个i, j两个下标，同时对序列进行扫描，以O(n)复杂度解决问题的一种思想

2024-01-02 09:09:40

two pointers思想 ---- 利用两个i, j两个下标，同时对序列进行扫描，以O(n)复杂度解决问题的一种思想, 如果能用这种思想解决问题，那么会大大降低程序的复杂度。

两个利用这个思想的例子：

分析：

代码：

 1 while (i < j){
 2         if (a[i] + a[j] == m){
 3             printf("%d %d\n", i, j);
 4             i++;
 5             j++;
 6         }
 7         else if (a[i] + a[j] < m){
 8             i++;
 9         }
10         else{
11             j++;
12         }
13     }

思路：

代码：

 1 int merge(int A[], int B[], int C[], int n, int m){
 2     int i = 0, j = 0, index = 0;        // i指向A[0], j指向B[0]
 3     while (i < n && j < m){
 4         if (A[i] < B[j]){
 5             C[index++] = A[i++];
 6         }
 7         else if (A[i] > B[j]){
 8             C[index++] = B[j++];
 9         }
10         else{
11             C[index++] = A[i++];
12             j++;
13         }
14     }
15 
16     while (i < n)
17         C[index++] = A[i++];        // 将序列A的剩余元素加入序列C
18     while (j < m)
19         C[index++] = B[j++];        // 将序列B的剩余元素加入序列C
20 
21     return index;
22 }

如果两个索引下标 i 和 j 指向的是同一个序列，那么这两个索引的移动方向一共有四种情况

1. i 和 j 都从0开始向(n - 1)移动，只是移动的速度不一样

2. i 和 j 都从(n - 1)开始向0移动，只是移动速度不一样

3. i 和 j 分别从0 和（n - 1）向中间移动（前面的例子1就是这种情况）

4. i 和 j 都从序列的中间 n / 2 分别向0 和 n - 1两头移动

实战1：

前面用二分法解决过 PAT 的 B1030 题目，现在再用two pointers方法实现一遍：

　　　　　　　　　　　　　　1030 完美数列 (25分)

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

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

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

思路：

注意点：

代码实现：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int a[100010];
 6 int main()
 7 {
 8     freopen("in.txt", "r", stdin);
 9     int n, p;
10     scanf("%d %d", &n, &p);
11     for (int i = 0; i < n; i++){
12         scanf("%lld", &a[i]);
13     }
14 
15     sort(a, a + n);
16 
17     int i = 0, j = 0, count = 1;
18     while (i < n && j < n){
19         // j不断右移，直到恰好不满足条件
20         while (j < n && a[j] <= (long long)a[i] * p){
21             count = max(count, j - i + 1);
22             j++;
23         }
24         i++;        // i右移一位
25     }
26 
27     printf("%d\n", count);        // 输出结果
28 
29     fclose(stdin);
30     return 0;
31 }

实战2：

求两个序列的中间数 (PAT A1029)

　　　　　　　　　　　　　　1029 Median (25分)

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×105) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output Specification:

For each test case you should output the median of the two given sequences in a line.

Sample Input:

4 11 12 13 14
5 9 10 15 16 17

Sample Output:

13

思路：（两种方法）
法一：现将两个序列用two pointers方法混合成一个新的序列，再取出新序列的中间值

法一代码：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 int s1[200010], s2[200010];
 7 int s3[400020];
 8 
 9 // 混合函数
10 void merge(int A[], int B[], int C[], int n1, int n2){
11     int i = 0, j = 0, index = 0;
12     while (i < n1 && j < n2){
13         if (A[i] < B[j]){
14             C[index++] = A[i++];
15         }
16         else if (A[i] > B[j]){
17             C[index++] = B[j++];
18         }
19         else{
20             C[index++] = A[i++];
21             j++;
22         }
23     }
24 
25     while (i < n1)
26         C[index++] = A[i++];
27     while (j < n2)
28         C[index++] = B[j++];
29 }
30 
31 
32 int main()
33 {
34     freopen("in.txt", "r", stdin);
35     int n1, n2;
36     scanf("%d", &n1);
37     for (int i = 0; i < n1; i++){
38         scanf("%d", &s1[i]);
39     }
40     
41     scanf("%d", &n2);
42     for (int i = 0; i < n2; i++){
43         scanf("%d", &s2[i]);
44     }
45     
46     merge(s1, s2, s3, n1, n2);
47     if (n1 == 0 && n2 == 0)
48         printf("0\n");
49     else
50         printf("%d\n", s3[(n1 + n2 - 1) / 2]);
51 
52     fclose(stdin);
53     return 0;
54 }


法二：由于两个序列的长度都是已知的，所以中间值的位置就是确定的(m + n - 1) / 2，所以只需用two pointers方法不断对两个序列去最小值，直到最小值的位置是中间值的位置为止，这里要注意一点，最终输出的结果必须是s1[i]和s2[j]中的较小者。

法二代码：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int inf = 1 << 30;
 6 
 7 int s1[200010], s2[200010];
 8 
 9 
10 int main()
11 {
12     freopen("in.txt", "r", stdin);
13     int n1, n2;
14     scanf("%d", &n1);
15     for (int i = 0; i < n1; i++){
16         scanf("%d", &s1[i]);
17     }
18 
19     s1[n1] = inf;
20 
21     scanf("%d", &n2);
22     for (int i = 0; i < n2; i++){
23         scanf("%d", &s2[i]);
24     }
25     s2[n2] = inf;
26 
27     // 中位数所在的位置下标
28     if (n1 == 0 && n2 == 0){
29         printf("0\n");
30         return 0;
31     }
32 
33     int medianPos = (n1 + n2 - 1) / 2;
34     int i = 0, j = 0, index = 0;
35     while (index < medianPos){
36         if (s1[i] < s2[j]) 
37             i++;
38         else
39             j++;
40         index++;
41     }
42 
43     if (s1[i] < s2[j])
44         printf("%d\n", s1[i]);
45     else
46         printf("%d\n", s2[j]);
47 
48     fclose(stdin);
49     return 0;
50 }

1029 Median 1029位数

码农公寓