多指针法
← 内容总览 03 / 24 下一节 → 强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 多指针法
对比枚举法，多指针法的精髓在于其高效的“剪枝”能力，而这种能力完全来自于指针移动的“规则”。这个规则通常基于数组的有序性等已知条件。例如，在合并两个升序数组时，规则是“取较小值，移动其指针”。这个简单的规则保证了我们每次选择的都是当前所有未合并元素中的最小值，从而无需比较所有未合并的元素。我们之所以敢于只移动一个指针，是因为我们确信被“跳过”的那个数组中的其他元素(在该指针之后的元素）必然比当前选中的元素更大，不可能成为下一个合并的元素。这种基于规则的确定性移动，让我们一次性地排除了大量的比较，实现了从O((m+n)^2)到O(m+n)的飞跃。可以说，找到并证明这个“规则”的正确性，是使用多指针法解决问题的关键。
多指针法考虑三个要点：指针起始位置、移动规则、停止处理。
## 类型1：多个有序顺序表
这是多指针法最经典的应用场景。通过在每个有序表上设置一个指针(可能在头或尾)，并根据特定规则移动它们，可以高效地解决多种问题。我们从以下题目中感受：
例题2-2：给定升序数组 A、B，长度分别为 n、m，合并成一个新的升序数组C 并输出。
例如：A = {1, 2, 7}，B = {3,4, 5}
枚举法：最暴力的枚举是，为了确定新数组C的下一个元素，我们需要比较A和B中还剩下的所有元素，然后找出最小的。确定第二个元素时，又要重复这个过程。这显然是低效的，时间复杂度为 O((m + n)2)。
<!-- page 24 -->
多指针法：在枚举法的基础上，发现升序条件没有用到，数组A、B、C都会是升序数组，因此数组C的下一个元素一定是数组A中最小元素及数组B 中最小元素其中较小的那个。最小元素在升序数组中是最左侧元素，所以设置两个指针分别指向A、B现存最小元素，每次比较指针所指元素并移动即可，时间复杂度 O(m+n)。
分析：数组C需要是升序，元素是从小到大存放，下一个元素一定是数组A中最小元素及数组B中最小元素其中较小的那个。所以每个数组的指针都应该分别指向他们还未处理的最小元素(即最左侧的下标)。 道
起始位置：数组 A、B、C的指针都是从左侧开始向右移动。
规则：比较数组A、B对应指针所指的元素，将较小的元素复制到结果数组中，然后将该较小元素所在的数组的指针、最终数组的指针各移动一位。不断重复这个过程。这个规则保证了结果数组始终是升序的，因为我们每次都选取了当前所有待选元素中的最小值。
停止处理：当其中一个数组的指针移出数组（即遍历完该数组的所有元素）时，退出循环。此时，另一个数组中可能还有剩余的元素，由于原数组是有序的，这些剩余元素必然都大于等于已合并的所有元素。因此，只需将这个数组的剩余部分依次复制到结果数组的末尾即可。 道
void Merge ( int A [], int n , int B [], int m )
{
int C [ n + m ];
int i = 0 , j = 0 , k = 0 ;
//直到有一个数组遍历完退出循环
while ( i & lt ; n & amp ; & amp ; j & lt ; m )
if ( A [ i ] & lt ; B [ j ])
C [ k ++ ] = A [ i ++ ];
else
C [ k ++ ] = B [ j ++ ];
//复制A 中剩余的元素
while ( i & lt ; n )
C [ k ++ ] = A [ i ++ ];
//复制B 中剩余的元素
while ( j & lt ; m )
C [ k ++ ] = B [ j ++ ];
从左到右输出数组C中的元素
}
例如 ： A = { -4 , -2 } B = { 0 , 1 , 3 } → C = { 16 , 9 , 4 , 1 , 0 } 。
void mergeAndSquare ( int A [], int n , int B [], int m )
{
int C [ n + m ];
int i = 0 ; // A 的指针，从左向右
int j = m - 1 ; // B 的指针，从右向左
int k = 0 ; // C 的指针，从左向右
// 直到有一个数组遍历完退出循环
while ( i & lt ; n & amp ; & amp ; j & gt ; = 0 )
if ( abs ( A [ i ]) & gt ; abs ( B [ j ]))
{
C [ k ++ ] = A [ i ] * A [ i ];
i ++ ;
}
else
{
C [ k ++ ] = B [ j ] * B [ j ];
j -- ;
}
// 复制 A 中剩余元素的平方
while ( i & lt ; n )
{
C [ k ++ ] = A [ i ] * A [ i ];
i ++ ;
}
// 复制 B 中剩余元素的平方
while ( j & gt ; = 0 )
{
C [ k ++ ] = B [ j ] * B [ j ];
j -- ;
}
// 输出 C...
}
void squareAndSort ( int A [], int n )
{
int B [ n ];
int i = 0 , j = n - 1 ; // 头尾指针
int k = 0 ; // B 指针，从后往前
//直到指针相遇退出循环
while ( i & lt ; = j )
{
if ( abs ( A [ i ]) & gt ; abs ( A [ j ]))
{
B [ k ++ ] = A [ i ] * A [ i ];
i ++ ;
}
else
{
B [ k ++ ] = A [ j ] * A [ j ];
j -- ;
}
}
// 输出 B...
}
void ans ( int A [], int n )
{
int i = 0 , j = n - 1 ;
int pivot = A [ 0 ];
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ;
if ( i & lt ; j ) swap ( A [ i ], A [ j ]); // A[j]<pivot<A[i]，交换
}
swap ( A [ 0 ], A [ i ]); //基准归位
}
void ans ( int A [], int n )
{
int L = 0 , R = n - 1 ; // L和R是当前处理区间的边界
while ( true )
{
int i = L , j = R ;
int pivot = A [ L ];
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ;
if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
}
swap ( A [ L ], A [ i ]);
if ( i == n / 2 ) return ;
if ( i & lt ; n / 2 ) L = i + 1 ; // 继续处理右区间
else R = i - 1 ; //继续处理左区间
}
}
← 内容总览 03 / 24 下一节 →