漫畫：什麼是字典序演算法？
————— 第二天 —————
演算法題目：
給定一個正整數，實現一個方法來求出離該整數最近的大於自身的「換位數」。
什麼是換位數呢？就是把一個整數各個數位的數字進行全排列，從而得到新的整數。例如53241和23541。
小灰也不知道這種經過換位的整數應該如何稱呼，所以姑且稱其為「換位數」。
題目要求寫一個方法來尋找最近的且大於自身的換位數。比如下面這樣：
輸入12345，返回12354
輸入12354，返回12435
輸入12435，返回12453
小灰發現的「規律」：
輸入12345，返回12354
12354 - 12345 =9
剛好相差9的一次方
輸入12354，返回12435
12435 - 12354 =81
剛好相差9的二次方
所以，每次計算最近的換位數，只需要加上9的N次方即可？
————————————
舉一個栗子：
給定1,2,3,4,5這幾個數字。
最大的組合：54321
最小的組合：12345
比如給定整數12354，如何找到離它最近且大於它的換位數呢？
為了和原數接近，我們需要盡量保持高位不變，低位在最小的範圍內變換順序。
那麼，究竟需要變換多少位呢？這取決於當前整數的逆序區域。
如果所示，12354的逆序區域是最後兩位，僅看這兩位已經是當前的最大組合。若想最接近原數，又比原數更大，必須從倒數第3位開始改變。
怎樣改變呢？12345的倒數第3位是3，我們需要從後面的逆序區域中尋找到剛剛大於3的數字，和3的位置進行互換：
互換後的臨時結果是12453，倒數第3位已經確定，這時候最後兩位仍然是逆序狀態。我們需要把最後兩位轉變回順序，以此保證在倒數第3位數值為4的情況下，後兩位儘可能小：
這樣一來，我們就得到了想要的結果12435。
獲得最近換位數的三個步驟：
1.從後向前查看逆序區域，找到逆序區域的前一位，也就是數字置換的邊界
2.把逆序區域的前一位和逆序區域中剛剛大於它的數字交換位置
3.把原來的逆序區域轉為順序
這種解法擁有一個高大上的名字：字典序演算法。
幾點補充：
本漫畫純屬娛樂，還請大家盡量珍惜當下的工作，切勿模仿小灰的行為哦。
系列文章：
《漫畫：什麼是一致性哈希？》
《漫畫：什麼是B+樹？》
《漫畫：什麼是B-樹？》
《漫畫：什麼是跳躍表？》
《漫畫：什麼是動態規劃？》
《漫畫：當程序猿遇上智力測試題》
《漫畫：判斷 2 的乘方》
《漫畫演算法：最小棧的實現》
《漫畫：什麼是大數據？》
《漫畫演算法：無序數組排序後的最大相鄰差值》
《漫畫：什麼是Bitmap演算法？》
《漫畫：Bitmap演算法 進階篇》
《什麼是A*尋路演算法？》
《漫畫：當程序員遇上智力題（第四季）》
《漫畫：什麼是紅黑樹？》
《漫畫：什麼是八皇后問題？》
●編號623，輸入編號直達本文
●輸入m獲取文章目錄
推薦↓↓↓
大數據與人工智慧
更多推薦《18個技術類公眾微信》
涵蓋：程序人生、演算法與數據結構、黑客技術與網路安全、大數據技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。
TAG:演算法與數據結構 |