「我一開始拿到題目的時候一點思路也沒有。後來經人提示才發現實際上這是一道披著 sort 外衣的 graph 題目。」
最近我的小夥伴問了一道題非常有趣。題目不難，但是我之前從來沒有遇到過，所以好好研究了一下。現在分享給大家，有更好的解法的同學可以指點我，如果沒見過這題的我們可以一起探討。
這題最開始是在 Google 的 phone screen 中被問到的。網上也有不少討論。
題目
原題如下：
Input: [1, 3, 4, 2]Output: 2Explanation: [1, 3, 4, 2] -> [1, 2, 4, 3] -> [1, 2, 3, 4]例如 input 是 [1, 3, 4, 2]。第一次選 3 那麼就是把 3 和從左到右第 index=2 的數也就是 2 互換。得到 [1, 2, 4, 3]。第二次選 4 那麼就是4 和從左到右第 index=3 個數也就是 3 互換。得到[1, 2, 3, 4] 是上升序列。所以 output 是 2（最少換了2次）。
我一開始拿到題目的時候一點思路也沒有。後來經人提示才發現實際上這是一道披著 sort 外衣的 graph 題目。
我們來看 input [1, 3, 4, 2]
① 先試著排一下序看看會發生什麼。
排序後的 index 0 3 1 2
已經排序後的數組 [1, 2, 3, 4]
② 找規律發現：
num 1: 0 → 0
num 3: 1 → 2
num 4: 2 → 3
num 2: 3 → 1
總結髮現實際上這就變成了一個有 4 個 vertex 的 graph。
那麼接下來怎麼推進呢？
不慌，我們先來複習一下 graph 的定義。
Graph 定義
對於 graph G = (V, E) 主要包括兩點：
vertex（V）：頂點
edge（E）：邊
一邊有單向 graph 和雙向 graph 之分。
現在回到我們的題目，雖然看上去互換（swap）非常迷惑，感覺非常像雙向 graph，但實際上這是一個單項 graph 就可以解決的題目。
解題思路
所以我的思路如下，用標準的 DFS 來遍歷這個 graph 即可。
①首先建立 graph (index, num)
[(0, 1), (1, 3), (2, 4), (3, 2)]
② 根據 num 排序
[(0, 1), (3, 2), (1, 3), (2, 4)]
③ for loop 這個數組，遇到當前 i 和 index 不一致的就 DFS 一直往下找。每遍歷新的一個 vertex 就記錄一次 swaps。總的 swaps 應該是遍歷的 edge，所以應該是 vertex 的遍歷數 - 1。這個環節的技巧是利用 graph 反向推導。即從 sorted input 還原到最開始 original position 需要多少 swap。因為 original order 是已知條件。
// pseudo codevisited = {};
for i, [0 -> 4): if(sortedInput[i][0] == i || visited[i]){ // skip current index continue; } vertex = i; swaps = 0; while(!visited[vertex]){ visited[vertex] = true; // DFS 一直遍歷到底 vertex = sortedInput[vertex][0]; swaps += 1; } if(swaps > 0){ total += swaps - 1; }我還總結了很多類似的 LeetCode 解題技巧，可以公眾號回復「刷題「獲取。
下面的手稿是 input = [2, 4, 5, 1, 3] 的演算過程。
總結
首先是複雜度分析。
Time Complexity: O(NlogN) N 表示遍歷 N 個節點；logN 表示排序
Space Complexity: O(N) 需要保存當前已經訪問過的 vertex
遇到類似的題如果正面推不出來，可以考慮反面推。先把 input 排個序。兩個解題要點：1）先把 graph 建起來。2）在這個基礎上倒推回原來的 original 數組 list。
原始碼就不貼出來了，如果大家有需要或者還沒看明白也可以聯繫我。同時歡迎指出錯誤，我們一起進步。
Google | Phone Screen | Min Swaps to Sort Array
如果你對其他的算法學習也感興趣，可以公眾號回復」算法「深入了解。
自我提升 | 編程規劃 | 美國生活
你若喜歡，為小老虎點個在看哦