雙指標就是這麼簡單
一、背景
這篇文章主要介紹雙指標的一些使用場景。
看之後可以發現,原來雙指標使用簡單速度高效。
二、雙指標簡介
雙指標的含義是陣列中的兩個指標,也可以是陣列的兩個下標。
雙指標一般有兩種用法。
第一種是一個指標從頭向後移動,另一個指標從尾部向前移動。
第二種是兩個指標抖從頭部向後移動,但是一個移動的快,一個移動的慢。
下面分別來看看對應的實際使用場景吧。
三、反轉字串
如果你認真看我上篇文章《 字串就是這麼簡單 》的話,可以發現在第一個例子“二進位制求和”中,我們多次用到字串反轉。
在程式碼裡我直接使用了 STL 自帶的反轉函式 std::reverse
。
現在我們需要自己來實現這樣一個函式。
面對這道問題,最簡單粗暴的方案就是新開一個數組,迴圈一遍即可,複雜度 O(n)
。
我們使用雙指標技術,則可以找到一個更優的方案,複雜度雖說也是 O(n)
,但是計算相同的資料,速度提高了一倍。
具體來說,迴圈陣列時,使用兩個下標,一個指向首部,一個指向尾部。
每次先判斷是否已經完成反轉,未完成則交換兩個下標的值,然後頭部下標向後移,尾部下標向前移。
等完成反轉後,我們可以發現頭部下標迴圈了陣列的前半部,尾部下標未還了陣列的後半部。
四、陣列拆分 I
告訴你 2n
個數字,將這些數字劃分為 n
對,例如 (a1, b1), (a2, b2), ..., (an, bn)
。
求一種劃分,使得 1
到 n
的 min(ai, bi)
的和最大。
這道題的題意使用人話說,就是將數字兩兩劃分後,在每對數字裡面選最小的數並求和,求和最大的劃分。
由於每對都取最小的數字,可以確定,所有數字裡面最小的數字肯定會被選出來。
接著這個最小的數字可以免費帶走一個數字,那我們肯定選擇帶走第二小的數字啦。
按照這個邏輯來,這道題的思路也就出來了。
先把所有數字從小到大排序,假設下標從 0
開始,我們只挑選偶數下標的數字即可。
五、兩數之和 II
題意:輸入一個按照升序排序的陣列,求找兩個不同的數字,使得他們的和等於目標數字。
這道題雖然很簡單,但是很有意思。
因為可以實現的方法特別多,可以當做面試題來考察對方。
面對這道題,第一個可以想到的方案就是列舉暴力查詢。
即迴圈假設選擇第一個數,然後在後面迴圈查詢是否存在答案。
由於有兩層迴圈,複雜度是 O(n^2)
。
當我們問是否可以優化時,可以發現後面迴圈查詢可以優化。
我們的目標是判斷第一個數字和第二個數字之和是否是目標數字。第一個數字和目標數字已經確定了,可以反向計算出第二個數字的值。
待查詢的陣列是有序的,自然可以使用二分查找了。
這裡最外層一層迴圈,裡面二分查詢,複雜度是 O(n*log(n))
。
PS:我之前曾介紹過《 二分查詢 》,感興趣的可以去看看。
我們使用了二分查詢提高了查詢速度,那我們能不能更快的解決這個問題呢。
這就需要研究一下這道題的特徵了。
特徵一、陣列有序。
特徵二、求兩數字的和等於目標數字。
假設我們選擇的第一個數字是從小到大的,例如選擇了下標為 0
的數字。
如果與最後一個數字之和大於目標,是不是意味著第一個數字不管選哪個,最後一個數字都不會是答案呢?
既然最後一個數字不可能是答案,是不是我們可以將陣列的範圍減小一些呢?
每次選擇第一個數字後,我們依次更新陣列的邊界,直到之和小於等於目標。
等於了則找到答案了,結束。小於了則代表選擇的這個數字沒有答案,迭代到下個數字去。
按照這個思路來看這道題,突然發現找到了一個新大陸:這道題竟然可以在 O(n)
複雜度內完成計算。
六、移除元素
題意:給你一個數組,將所有陣列值等於 val
的元素刪除,並返回新陣列的長度。
要求:刪除過程中,不能申請新的陣列,原陣列的長度也不能變。
這道題顯然是一個面試題了。
如果允許改變原陣列的長度,那找到一個直接刪除一個就行了,時間複雜度是 O(n^2)
。
如果允許申請新陣列,那迴圈一遍即可得到新的陣列,但需要額外的空間複雜度是 O(n)
。
現在不能申請新陣列,那隻能在原陣列上進行操作了。
假設我們找到了一個元素後,目標用其他位置的元素覆蓋當前元素。
一種思路是馬上覆蓋,另一種是延遲覆蓋。
對於馬上覆蓋的方法,說出來就很容易理解。
當前元素直接和最後一個元素交換,然後陣列的大小減一,然後重新從當前位置進行判斷計算。
什麼?不能改變陣列的大小?使用另外一個指標或者下標儲存這個大小即可。
此時雙指標一個是頭下標,一個是尾下標。
PS:這個思想面試中經常會遇到,比如數組裡隨機選幾個數字。
另一個思路是延遲覆蓋。
具體含義即使當前這個位置先空著,後面找到需要覆蓋的值了,再來覆蓋。
這個時候,用一個下標來標記空的位置,用另外一個下標來標記查詢的位置。
七、最大連續1的個數
題意:給一個 0/1
陣列,求最大連續 1
的個數。
這已經是第三次遇到 0/1
相關的題目了。
這道題也是有多種方法來解決。
一種就計數法,一種就是當前的主題兩指標法。
計數法沒遇到零則重置計數,遇到一則加1,並更新答案即可。
兩指標方法和計數類似,遇到零重置指標,遇到一則偏移指標。
在這兩個方法裡,都可以看到在最後有一個特殊判斷。這是由於陣列可能以 1
結束,最後一個答案就沒有進行計算。
其實,這個稍微調整一下,就不需要考慮特殊情況了。
八、長度最小的子陣列
題意:給一個正陣列成的陣列和一個正整數 S
,求一個長度最小的連續子陣列,使得它們的和大於等於 S
。
對於這道題,也是一道面試題。
最簡單粗暴的方法就是求出所有的連續子陣列,找到最優答案,複雜度 O(n^2)
。
這個就不上程式碼了。
面對那麼暴露的方案,我們其實位置確定後,目標是快速找到滿足條件的結束位置。
那能不能使用二分呢?
這裡是檢查子陣列的和,每次子陣列的起始位置不一樣。
但是我們發現,對於確定的一次查詢,那些子陣列的和都是字首陣列和減去固定起始位置的字首陣列 presum
。
於是問題就可以轉化為:求字首陣列和大於 S+presum
的最小位置。
而對於字首陣列和,是可以預處理求出所有的字首陣列和,然後二分的。
此時,再分析一下這道題,會發現有意思的特徵。
假設已經判斷 a[i] + a[i+1] ... + a[k]
首次大於等於 S
了。
接下來需要查詢的是以 a[i+1]
為起點的陣列。
仔細看看 a[i]
計算的和,可以發現 a[i]+...+a[k]
已經計算過了,且 a[i]+...+a[k-1]
一定小於 S
。
那我們是不是隻需要直接從 a[i+1] +... a[k]
開始計算是否是答案就行了?
這樣下來,我們就只需要掃描一遍即可找到最優答案了。
至於 a[k]
的位置,我們使用另外一個指標或者下標來標記維護即可。
九、最後
回頭看看,這個文章裡面涉及到的題,都可以哪來當做面試題。
暴力方法是 O(n^2)
,優化後可以到 O(n*log(n))
,再優化就可以到 O(n)
了。
這樣的題還有很多,不要想著把這題背下來,而是要學會掌握解決這類問題的思想或者方法。
否則前面出一道很難的背過的題快速答上來了,後面出一道簡單的題怎麼也答不上來,那很容易判斷前面的題是從面試寶典上背的了。
-EOF-