Codewars Next bigger number with the same digits (Python) на сайте вылетает с ошибкой Execution Timed Out (12000 ms). В чем ошибка?
Задача звучит: Create a function that takes a positive integer and returns the next bigger number that can be formed by rearranging its digits. For example:
12 ==> 21 513 ==> 531 2017 ==> 2071 If the digits can't be rearranged to form a bigger number, return -1 (or nil in Swift, None in Rust):
9 ==> -1 111 ==> -1 531 ==> -1
def next_bigger(n):
import itertools
a=0
b=0
spisok_1=list(map(int, str(n)))
spisok_2=list(itertools.permutations(spisok_1, len(spisok_1)))
spisok=[]
for el in spisok_2:
string = ''
for i in range(len(el)):
string+=str(el[i])
i+=1
spisok.append(int(string))
spisok = list(dict.fromkeys(spisok))
spisok.sort()
a = spisok.index(n)
if int(n) == int(spisok[-1]):
b = -1
else:
b = spisok[a + 1]
return int(b)
pass
print(next_bigger(531))
Ошибка: Execution Timed Out (12000 ms) Как можно оптимизировать код?
Ответы (1 шт):
Автор решения: Глeб
→ Ссылка
Ну, за разумное время задача решается так:
def next_bigger(num):
digits = [int(i) for i in str(num)]
ind = len(digits) - 1
while ind >= 1 and digits[ind - 1] >= digits[ind]:
ind -= 1
if not ind:
return -1
pivot = digits[ind - 1]
swap_ind = len(digits) - 1
while pivot >= digits[swap_ind]:
swap_ind -= 1
digits[swap_ind], digits[ind - 1] = digits[ind - 1], digits[swap_ind]
digits[ind:] = digits[:ind - 1:-1]
return int(''.join(str(x) for x in digits))
Вывод:
1234567989
531
2071
-1
-1
-1
В решении используется Next lexicographical permutation algorithm.
Немного более красивый (но не такой быстрый) алгоритм:
def next_bigger(n):
s = list(str(n))
for i in range(len(s) - 2, -1, -1):
if s[i] < s[i+1]:
t = s[i:]
m = min(filter(lambda x: x > t[0], t))
t.remove(m)
t.sort()
s[i:] = [m] + t
return int("".join(s))
return -1