隨筆檔案

兩個(gè)指針的作用

兩個(gè)指針一般用在一個(gè)序列中。
在一個(gè)序列中處理問(wèn)題時(shí)，如果只使用一個(gè)指針，可能會(huì)造成雙重循環(huán)的問(wèn)題，結(jié)果時(shí)間復(fù)雜度會(huì)是 O(N) 。
如果采用兩個(gè)指針可以很好地解決問(wèn)題，時(shí)間復(fù)雜度也可以得到改進(jìn)。

采用兩個(gè)指針的例子很多，這里舉幾個(gè)：
1.
自動(dòng)文摘中，如果采用循環(huán)查找的方法，時(shí)間復(fù)雜度是冪次方。采用兩個(gè)指針，分別指向文摘的開(kāi)始處和結(jié)束處可以在 O(N) 的時(shí)間復(fù)雜度內(nèi)找到文摘。

2.
求連續(xù)數(shù)字之和等于一給定數(shù)，例如給定數(shù)是 15 ，則結(jié)果有 1 2 3 4 5、4 5 6、7 8 三種結(jié)果。
如果采用循環(huán)的方法事件復(fù)雜度是 O(N^2)
可以采用兩個(gè)指針，分別指向 small 和 big 。當(dāng) sum(small ... big) 大于給定數(shù)時(shí)，small 指針右移，當(dāng) sum 小于給定數(shù)時(shí)，big 指針右移。直到 small 是給定數(shù)的一半時(shí)。

3.
調(diào)整數(shù)組，是前半部分是某種類型的數(shù)，后半部分是某種類型的數(shù)。
比如前半部分是奇數(shù)，后半部分是偶數(shù)
前半部分是負(fù)數(shù)，后半部分是非負(fù)數(shù)
采用兩個(gè)指針，分別從左右兩端進(jìn)行掃描，檢測(cè)，如果符合條件則交換兩數(shù)，直到兩個(gè)指針交叉為止。

4.
求一個(gè)數(shù)組中兩個(gè)數(shù)的和等于一定數(shù)。
先對(duì)數(shù)組排序
然后從數(shù)組兩端用兩個(gè)指針掃描，檢測(cè)，直到兩個(gè)指針交叉為止。

當(dāng)一個(gè)指針無(wú)法很好解決問(wèn)題時(shí)，應(yīng)該再增添一個(gè)指針，多一個(gè)幫手。