天天看點

ACM之下一個更大元素

題目如下:

ACM之下一個更大元素

将這個問題考慮三種情況:

1)如果輸入的正整數n的每一位都按照降序排列,則肯定不存在滿足題意的數,傳回-1。例如54321

2)如果輸入的正整數n的每一位都按照升序排列,則隻需要将最後兩位調換位置即可。例如123456→123465

3)其他情況,因為需要找滿足題意的最小數,是以從右往左處理數字(即從低位到高位)

前兩種情況容易完成,我們來讨論第三種情況,也就是解決這道題的關鍵算法:

Ⅰ. 從右往左周遊整數的各個位,直到找到前一位的數字小于後一位的數字。比如,輸入的數為:543976,則周遊到3時停止,我将這個位置叫做停止位,因為3小于後一位9;如果找不到這樣的數,則該數不滿足題意,傳回-1

Ⅱ. 然後找到停止位右邊的位數中最小的數,将其與停止位交換。543976的停止位是3,3右邊的位數是976,位數中最小的數是6,是以将6與3交換,這樣就保證在停止位上的數是滿足題意的最小數,

Ⅲ. 然後将停止位右邊的位數按升序排列(将大數往低位放,進而得到最小數)。比如543976 → 546973 → 546379,傳回546379即可

Java實作