【邊玩邊學】：漫畫圖解字典序算法

————— 第二天 —————

算法題目：

給定一個正整數，實現一個方法來求出離該整數最近的大於自身的“換位數”。

什麼是換位數呢？就是把一個整數各個數位的數字進行全排列，從而得到新的整數。例如53241和23541。

小灰也不知道這種經過換位的整數應該如何稱呼，所以姑且稱其為“換位數”。

題目要求寫一個方法來尋找最近的且大於自身的換位數。比如下面這樣：

輸入12345，返回12354

輸入12354，返回12435

輸入12435，返回12453

小灰髮現的“規律”：

輸入12345，返回12354

12354 - 12345 = 9

剛好相差9的一次方

輸入12354

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.把原來的逆序區域轉為順序

//主流程，返回最近一個大於自身的相同數字組成的整數。public static int[] findNearestNumber(int[] numbers){ //拷貝入參，避免直接修改入參 int[] numbersCopy = Arrays.copyOf(numbers, numbers.length); //1.從後向前查看逆序區域，找到逆序區域的前一位，也就是數字置換的邊界 int index = findTransferPoint(numbersCopy); //如果數字置換邊界是0，說明整個數組已經逆序，無法得到更大的相同數字組成的整數，返回自身 if(index == 0){ return null; } //2.把逆序區域的前一位和逆序區域中剛剛大於它的數字交換位置 exchangeHead(numbersCopy, index); //3.把原來的逆序區域轉為順序 reverse(numbersCopy, index); return numbersCopy;}private static int findTransferPoint(int[] numbers){ for(int i=numbers.length-1; i>0; i--){ if(numbers[i] > numbers[i-1]){ return i; } } return 0;}private static int[] exchangeHead(int[] numbers, int index){ int head = numbers[index-1]; for(int i=numbers.length-1; i>0; i--){ if(head < numbers[i]){ numbers[index-1] = numbers[i]; numbers[i] = head; break; } } return numbers;}private static int[] reverse(int[] num, int index){ for(int i=index,j=num.length-1; i 
這種解法擁有一個高大上的名字：字典序算法。
 

閱讀更多 java進階架構師 的文章

關鍵字: 動漫 算法 漫畫