主題
題目連結：
題目意譯：
你被給定一個字串 num 代表著一個很大的整數，以及一整數 k 。
我們稱某些整數很奇妙，如果其為 num 中的每位數字之一種排列且該數之值大於 num 。有可能有很多個奇妙數字。但是我們只考慮其中值最小的。
例如，當 num = "5489355142"：
第一小的奇妙整數為 "5489355214" 。
第二小的奇妙整數為 "5489355241" 。
第三小的奇妙整數為 "5489355412" 。
第四小的奇妙整數為 "5489355421" 。
回傳最小所需的 num 中的相鄰數字交換之次數，使其變為第 k 小的奇妙整數。
測試資料保證第 k 小奇妙整數存在。
限制：
2 ≦ num.length ≦ 1000
1 ≦ k ≦ 1000
num 只由數字組成。
範例測資：
範例 1：
輸入： num = "5489355142", k = 4
輸出： 2
解釋： 第 4 小的奇妙數字為 "5489355421"。為了得到這數字：
- 將索引值 7 與索引值 8 交換： "5489355142" → "5489355412"
- 將索引值 8 與索引值 9 交換： "5489355412" → "5489355421"
範例 2：
輸入： num = "11112", k = 4
輸出： 4
解釋： 第 4 小的奇妙數字為 "21111"。為了得到這數字：
- 將索引值 3 與索引值 4 交換： "11112" → "11121"
- 將索引值 2 與索引值 3 交換： "11121" → "11211"
- 將索引值 1 與索引值 2 交換： "11211" → "12111"
- 將索引值 0 與索引值 1 交換： "12111" → "21111"
範例 3：
輸入： num = "00123", k = 1
輸出： 1
解釋： 第 1 小的奇妙數字為 "00132"。為了得到這數字：
- 將索引值 3 與索引值 4 交換： "00123" → "00132"
解題思維：
直接利用這題的想法套用 k 次的「下一個排列」，即可求出 num 的第 k 小奇妙整數。也可以利用這題的想法先計算出 num 本身是字典序中第幾個排列（假設為 X），然後再直接求出第 X + k 個排列為何數，也就是第 k 小奇妙整數。
假設第 k 小奇妙數字為 target。則我們把 num 拿去與 target 一位一位比較（從左到右）。
當 num[i] ≠ target[i] 時，我們便從 k = i + 1 開始往右尋找到第一個 num[k] 等於 target[i]。找到之後我們便從 num[k] 一路慢慢地往 num[i] 交換過去（因為每次只能交換相鄰的數字），所以這裡一共會交換 k - i 次且 num[i + 1] ～ num[k - 1] 的數字會往右移動一個位置。
這樣子掃過之後，每一次的 num[i] ≠ target[i] 我們確保交換次數是盡可能地少的， 因此過程中的交換次數之總和即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
