問題描述
在Codewars對套路練習(xí)的分類中弓坞，這是一個難度為4的題目隧甚。難度數(shù)字越低，代表越困難渡冻。完成之后得到的積分戚扳，就越高。
你得編寫一個函數(shù)族吻，接受一個正整數(shù)作為輸入帽借，然后輸出由相同數(shù)字組成的下一個更大的數(shù)：
next_bigger(12)==21
next_bigger(513)==531
next_bigger(2017)==2071
如果找不到由相同數(shù)字組成的更大整數(shù)，則返回-1：
next_bigger(9)==-1
next_bigger(111)==-1
next_bigger(531)==-1
測試用例
Test.assert_equals(next_bigger(12),21)
Test.assert_equals(next_bigger(513),531)
Test.assert_equals(next_bigger(2017),2071)
Test.assert_equals(next_bigger(414),441)
Test.assert_equals(next_bigger(144),414)
問題標簽
算法 數(shù)字 字符串 整型數(shù)
問題鏈接
http://www.codewars.com/kata/55983863da40caa2c900004e/train/python
問題解答
解題思路
一開始超歌，我曾經(jīng)想的很簡單砍艾，計劃把全部數(shù)字的排列組合都算出來并按順序排列在列表中，然后找到給定數(shù)字在列表中的索引值巍举。如果索引值為列表的最后一位脆荷，則返回-1；如果不是懊悯，則返回更大一個索引位置的值蜓谋。
看上去思路很簡單，但是實現(xiàn)起來的效率很差炭分。首先桃焕，隨著數(shù)字變大，進行初步排列的時間會很長捧毛，因為會有很多種排列方法观堂；其次，在排列過程中呀忧，可能需要較大的內(nèi)存空間來保存過程中生成的列表师痕。最后的兩步操作的效率倒是還好。
綜合上面的考慮而账，沒有繼續(xù)按照這種思路實現(xiàn)胰坟。
最后，經(jīng)過嘗試和思考福扬，我找到了如下的思路：
首先腕铸，找到給定數(shù)字中，從右至左沒有按從大到小順序排列的一段數(shù)字铛碑。假如給定數(shù)字式987685432狠裹，那么沒有按順序排列的一段數(shù)字就是，685432汽烦。
然后涛菠，對找到的這段數(shù)字重新排列。先把給定數(shù)字變成兩個列表，[9,8,7]與[6,8,5,4,3,2]俗冻，然后對后面列表中的這些數(shù)字礁叔，取比6大一位的數(shù)字，即8迄薄。最后琅关，把除8以外的數(shù)字，按從小到大得順序重新排列讥蔽。
最后涣易，再把重排后的列表，與沒有變動的列表相加冶伞，組成最后的數(shù)字新症。
編程派的解法
具體實現(xiàn)如下：
:::python
def next_bigger(n):
to_list = list(int(i) for i in str(n))
length = len(to_list)
if length == 1:
return -1
i = -1
while to_list[i] <= to_list[i - 1]:
i -= 1
if i == -length:
return -1
process_list = to_list[i - 1:]
replace = 0
for num in sorted(process_list):
if num > process_list[0]:
replace = num
break
process_list.remove(replace)
result = to_list[:i - 1] + [replace] + sorted(process_list)
return int(''.join(str(i) for i in result))
網(wǎng)友解法摘錄
目前在Codewars.com，完成這道題目的網(wǎng)友只有389人响禽。
網(wǎng)友pavel.koshev：得到三個最佳實踐投票
:::python
def next_bigger(n):
n = str(n)[::-1]
try:
i = min(i+1 for i in range(len(n[:-1])) if n[i] > n[i+1])
j = n[:i].index(min([a for a in n[:i] if a > n[i]]))
return int(n[i+1::][::-1]+n[j]+''.join(sorted(n[j+1:i+1]+n[:j])))
except:
return -1
網(wǎng)友adam-tokarski
:::python
def next_bigger(n):
i, ss = n, sorted(str(n))
if str(n) == ''.join(sorted(str(n))[::-1]):
return -1;
while True:
i += 1;
if sorted(str(i)) == ss and i != n:
return i;