主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開始數(shù)的二維整數(shù)陣列 pairs，其中 pairs[i] = [starti, endi]。一個(gè) pairs 的排列是「合法的」，代表著對(duì)於每一個(gè)滿足 1 ≦ i < pairs.length 的索引值 i，endi-1 == starti 都成立。
回傳任意一個(gè) pairs 的合法排列。
注： 測(cè)資之生成保證存在至少一個(gè) pairs 的合法排列。
限制：
1 ≦ pairs.length ≦ 10 ^ 5
pairs[i].length == 2
0 ≦ starti, endi ≦ 10 ^ 9
starti != endi
沒有兩個(gè)數(shù)對(duì)完全一致。
存在至少一個(gè) pairs 的合法排列。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： pairs = [[5,1],[4,5],[11,9],[9,4]]
輸出： [[11,9],[9,4],[4,5],[5,1]]
解釋：
此排列是合法的，因?yàn)槊恳粋€(gè) endi-1 都等於 starti。
end0 = 9 == 9 = start1
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3
範(fàn)例 2：
輸入： pairs = [[1,3],[3,2],[2,1]]
輸出： [[1,3],[3,2],[2,1]]
解釋：
此排列是合法的，因?yàn)槊恳粋€(gè) endi-1 都等於 starti。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
[[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 之排列也是合法的。
範(fàn)例 3：
輸入： pairs = [[1,2],[1,3],[2,1]]
輸出： [[1,2],[2,1],[1,3]]
解釋：
此排列是合法的，因?yàn)槊恳粋€(gè) endi-1 都等於 starti。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
解題思維：
首先觀察一下合法排列的「長(zhǎng)相」。
以範(fàn)例測(cè)資一的答案為例：[[11,9],[9,4],[4,5],[5,1]]，把中括號(hào)刪光光之後會(huì)得到 11 9 9 4 4 5 5 1。
可以看到除了開頭和結(jié)尾的兩個(gè)數(shù)字以外的其他在中間的數(shù)字都是兩兩一組相同。因此不如就每?jī)蓚€(gè)數(shù)字省略掉其中一個(gè)。所以上面的答案會(huì)變成 11 9 4 5 1。
而這可以解讀成從數(shù)字 11 走到 9、再走到 4、其次是 4、再來是 5、最後是 1。而可以看到其中如「11 走到 9」對(duì)應(yīng)著原本的 [11,9] 之?dāng)?shù)對(duì)。
因此我們可以把輸入視為是數(shù)線上各個(gè)數(shù)字（只考慮有出現(xiàn)在 pairs 中的）作為頂點(diǎn)，然後以 pairs 作為整張圖的邊（注意，這些邊是「有向」的）。
而從題意可以得到，我們要在圖中找出「一筆劃走完所有邊」的路徑。以前在這題有提過一筆劃存在性的充分必要條件，但那個(gè)適用的是無向圖的情況。不過有向圖實(shí)際上還是類似，只是現(xiàn)在有邊本身有 in-degree（入邊）和 out-degree（出邊）之差別。
因此對(duì)於有向圖來說，一筆劃存在若且唯若
（一）「每一個(gè)頂點(diǎn)的出邊數(shù)等於入邊數(shù)」
或是
（二）「存在恰好一個(gè)頂點(diǎn)滿足出邊數(shù)減去入邊數(shù)等於 1，且存在恰好另一個(gè)頂點(diǎn)滿足出邊數(shù)減去入邊數(shù)等於 -1」
（以下用（一）和（二）代稱這兩個(gè)條件）
（實(shí)際上還有一個(gè)前置條件——這個(gè)有向圖必須至少是弱連通（Weakly Connected）的，也就是說將所有邊視為無向之後此圖是連通無向圖。不過這個(gè)條件通常會(huì)被無視，因?yàn)榻^大部分時(shí)候都已經(jīng)假設(shè)是弱連通有向圖了）
不過一筆劃實(shí)際上有兩種分類——一種是歐拉路徑（Eulerian Path）和歐拉迴路（Eulerian Circuit），前者是起點(diǎn)和終點(diǎn)不一定要同一個(gè)點(diǎn)，且（一）或（二）滿足時(shí)都可以找到；後者是起點(diǎn)和終點(diǎn)必定要是同一個(gè)點(diǎn)，且只有（一）滿足時(shí)才能找到。
而根據(jù)題意以及我們生成的圖之特性，題目必定會(huì)滿足（一）或是（二）其中一個(gè)，但不保證是其中哪一個(gè)。而（二）可以多加一條邊在滿足條件的這兩個(gè)點(diǎn)之間來變成（一）。所以我們可以先討論如何解決（一）。
有一種演算法叫做 Hierholzer's Algorithm，其精神如下：
既然給定的圖滿足（一），那隨便從任何一點(diǎn)開始都可以。稱其為 v。
可以看到一旦從 v 走出去之後便會(huì)「破壞」（一）的條件，此時(shí) v 的入邊比出邊多 1。而因此如果從 v 一直走一直走（無論經(jīng)過的點(diǎn)之前有沒有出現(xiàn)過），走到走不動(dòng)為止。此時(shí)停留點(diǎn)必定會(huì)是 v 本身。原因正是因?yàn)槠渌械狞c(diǎn)此時(shí)都還滿足（一），一旦走進(jìn)某個(gè)點(diǎn)（消耗它的入邊數(shù)）必定可以走出去（消耗它的出邊數(shù)）。唯獨(dú) v 因?yàn)樽钜婚_始走出去的行為而「多消耗了」一次出邊數(shù)。
此時(shí)可以得到一個(gè)迴路。但這個(gè)迴路不一定有經(jīng)過所有的邊。因此如果現(xiàn)在這個(gè)迴路上有點(diǎn) v' 存在使得還有「沒有使用過」的邊存在的話，則我們可以用 v' 作為「新的 v 點(diǎn)」然後重複以上步驟（當(dāng)然，是走那些還沒走過的邊）。
所以會(huì)得到舊的迴路 A 和新的迴路 B，而只要將 A 上的 v' 替換成整個(gè) B 即可將兩個(gè)迴路合併成單一一個(gè)。
即假設(shè) A 是 v → …… → v' → …… → v 、 B 是 v' → a → …… → b → v'，則合併後會(huì)是
v → …… → (v' → a → …… → b → v') → …… → v
重複這個(gè)找 v' 點(diǎn)的動(dòng)作直到所有邊都被使用過為止。
而因?yàn)閳D是弱連通圖（還記得那個(gè)「隱藏的」前置條件嗎？），這必定可以使用掉所有的邊。因此最後合併出來的迴路即為歐拉迴路。
如果上面的直覺說明不夠說服讀者的話。基本上上面的敘述的正確性可以由證明「某一個(gè)點(diǎn)被『走過』兩次以上的迴路，可以從該點(diǎn)拆成多個(gè)子迴路」、「兩個(gè)迴路交於至少一點(diǎn)，可以合併成一個(gè)迴路」、「弱連通的特性保證整個(gè)過程可以看過所有邊」即可完成。因?yàn)槲覒校栽诖耸÷浴?/div>
話雖如此，實(shí)際上要怎麼實(shí)作呢？
首先，我們需要存邊的資訊。用鄰接表（Adjacency List）即可（參見這題）。不過因?yàn)槲覀冃枰o(jì)錄每一個(gè)點(diǎn)哪些邊用過了，所以鄰接表還要加上一些額外的資訊。由於通常是用大小可變的陣列來實(shí)作鄰接表（例如說 C++ 的 vector）。而正因?yàn)槭顷嚵校虼酥苯用恳粋€(gè)點(diǎn)用一個(gè)變數(shù)紀(jì)錄現(xiàn)在看到哪一條邊即可。這樣一來每一個(gè)點(diǎn)不用每一次都重新掃過它的所有邊。
接著是觀察迴路的特性。假設(shè)我們從隨便一點(diǎn) v 一直走到不能走後回到 v，得到了 v → v' → v 這個(gè)迴路（這邊先不假設(shè)是用什麼資料結(jié)構(gòu)紀(jì)錄這個(gè)迴路，先叫它 S）。然後再假設(shè)這邊的 v' 跟上面的例子一樣有 v' → a → …… → b → v' 這個(gè)迴路。
可以看到結(jié)尾的那個(gè) v 確定不會(huì)再跟其他迴路合併了，因此可以安心地寫一個(gè) v 在某處紀(jì)錄最後整個(gè)歐拉迴路的結(jié)果（一樣，先不假定其資料結(jié)構(gòu)。先稱其為 V）。所以此時(shí) S = v → v' 、 V = v。
S 現(xiàn)在最後一個(gè)元素是 v'，則此時(shí)我們會(huì)根據(jù) v' 在鄰接表中還有沒有走過的邊。因此一樣繼續(xù)從 v' 走到不能走為止，然後得到了 v' → a → …… → b → v' 這個(gè)迴路。而因?yàn)槭菑?v'「長(zhǎng)」出來的，所以此時(shí) S = v → v' → a → …… → b → v'。
而跟前面的結(jié)尾 v 同理，此時(shí) S 結(jié)尾的 v' 也把邊掃完了。因此可以安心地寫下 v' 到結(jié)果中，此時(shí) V = v v' 且 S = v → v' → a → …… → b。
然後從 b 開始以此類推。
最後 S 會(huì)變成空的，而 V 會(huì)變成 v v' b …… a v' v。
此時(shí)的 V 就是所求的歐拉迴路。不過可以看到上面過程中是直接把新的元素丟到 V 的結(jié)果，因此實(shí)際上這個(gè)迴路跟預(yù)期的會(huì)「相反」。
因此可以直接使用一個(gè)支援前後都可以插入或刪除元素的資料結(jié)構(gòu)，例如說雙端佇列（Deque），然後把新的元素放在「前面」。又或是說用普通的動(dòng)態(tài)陣列把迴路反序存著，最後再整個(gè)反轉(zhuǎn)。抑或者是在當(dāng)初建立鄰接表時(shí)，把邊的方向先反轉(zhuǎn)。這樣子用動(dòng)態(tài)陣列存結(jié)果的時(shí)候不需要額外反轉(zhuǎn)一次。
方式族繁不及備載。範(fàn)例程式碼中是採(cǎi)取 S 用堆疊（Stack）實(shí)作（因?yàn)閺纳厦婵梢钥吹矫看问悄媒Y(jié)尾的點(diǎn)；不過同樣論述可以應(yīng)用開頭的點(diǎn)，所以其他資料結(jié)構(gòu)也可行）然後 V 是一個(gè)動(dòng)態(tài)陣列並採(cǎi)取將圖上的邊方向反轉(zhuǎn)的策略。
不過上面講述的是（一）的情況。（二）雖然加個(gè)邊便可以直接套用上面的方式做，但那個(gè)加上去的邊終究是假的。因此最後移除掉把元素挪位一下即可得到一個(gè)歐拉路徑。
例如說在範(fàn)例測(cè)資一中，我們會(huì)多加一條邊從 1 走到 11。因此會(huì)得到歐拉迴路 4 5 1 11 9 4（注意到上面的演算法會(huì)是隨便取最一開始點(diǎn)，所以可能會(huì)長(zhǎng)得不一樣）。由於 1 到 11 是假的邊，因此將這個(gè)迴路從那邊斷開得到 4 5 1 和 11 9 4 兩個(gè)路徑。
把右邊的路徑擺在後面、左邊的路徑擺在前面並將那個(gè)重複出現(xiàn)的 4 刪掉其中一個(gè)便可以得到 11 9 4 5 1。
但最後的最後，不要忘記題目所求不是上面求出來的歐拉迴路或歐拉路徑。那些走過的「邊」才是我們要的東西。
因此回到範(fàn)例測(cè)資一然後跑過上面的演算法會(huì)得到 11 9 4 5 1 這個(gè)路徑，而每?jī)蓚€(gè)數(shù)字代表著原本 pairs 中的一個(gè)數(shù)對(duì)，即 [11, 9] 、 [9, 4] 、 [4, 5] 、 [5, 1]。
所以最後再掃過一次歐拉路徑或迴路，便可以重建出原本要的 pairs 之合法排列，即所求。
而時(shí)間複雜度是「建立鄰接表」+「Hierholzer's Algorithm 之實(shí)作」+「重建答案」。
令E 為圖中的邊數(shù)（每一條邊即是一個(gè) pairs 中的數(shù)對(duì)，因此 E 恰好是 pairs.length）、 V 是圖中的點(diǎn)數(shù)（即 pairs 中有多少種數(shù)字，可以看到最多只會(huì)有 2E 個(gè)；而下界為 O(sqrt(E)) 個(gè)，因?yàn)轭}目限制有說到不會(huì)有兩個(gè)數(shù)對(duì)長(zhǎng)一模一樣。其中 sqrt(E) 是 E 的平方根）
「Hierholzer's Algorithm 之實(shí)作」因?yàn)橛杏妙~外的變數(shù)紀(jì)錄每一個(gè)點(diǎn)看哪些邊。因此每一個(gè)邊最多被看一次。所以這邊的時(shí)間是 O(E)。
「重建答案」只是單純地掃過一次歐拉路徑或迴路，因此時(shí)間是 O(E)。
至於「建立鄰接表」則因?yàn)閿?shù)值本身與 V 、 E 無關(guān)。根據(jù)本題的數(shù)值範(fàn)圍，不可能直接開與其範(fàn)圍大小相符的陣列。故這些數(shù)值需要「重新編號(hào)」（Re-indexing）。而這可以用雜湊表（Hash Table）來做到，也可以把所有數(shù)值排序並按照大小順序重新編號(hào)。前者「實(shí)務(wù)上」雖然會(huì)因?yàn)殡s湊碰撞次數(shù)不多而得到單次操作平均 O(1)，但最糟可以到 O(V)；後者因?yàn)橐判颍詴?huì)是 O(V log V)（雖然可以改用例如說基數(shù)排序法（Radix Sort）等非比較排序法，但時(shí)間複雜度的表示法中會(huì)包含數(shù)值範(fàn)圍本身。所以這邊怕各種討論的麻煩而忽略）。
因此最終時(shí)間複雜度會(huì)是 (平均 O(V) 的雜湊或是 O(V log V) 的排序) + O(E) + O(E)，即平均 O(E) 或是 O(E log E)。
題外話：這篇心得好長(zhǎng)。跟我預(yù)期的不太一樣 XD
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
