Two Pointer

· 类似一种技巧而非算法
· 使用两个下标对序列进行扫描,同向或反向视情况而定

给定序列从中求取a+b=m(m给定)

描述:给定一个递增的正整数序列和一个正整数M,求序列中的两个不同位置的数a和b,使得他们的和恰好为M,输出所有满足条件的方案。
二重枚举下复杂度O(n^2)
two pointer做法:

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

复杂度O(n);

序列合并问题

描述:假设有两个递增序列A与B,要求将他们合并为一个递增序列C。
two pointer做法:
设置两个下标i和j,初值均为0,表示分别指向序列A的第一个元素和序列B的第一个元素,然后根据A[i]与B[j]的大小来决定哪一个放入序列C

1
2
3
4
5
6
7
8
9
10
11
int merge(int A[],int B[],int C[],int n,int m){
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++]; //将序列A的剩余元素加入序列C
while(j<m) C[index++]=B[j++]; //………… B…………
return index; //返回序列C的长度
}

归并排序

快速排序