python - 优化 Python 函数以在 Codewars 上提交

Question

我有一个 this 的解决方案关于 codewars.com 的问题当我在 Sublime 中运行它时它有效，但是当我尝试提交时，我得到这个错误:

Process was terminated. It took longer than 12000ms to complete

Why did my code time out?

Our servers are configured to only allow a certain amount of time for your code to execute. In rare cases the server may be taking on too much work and simply wasn't able to run your code efficiently enough. Most of the time though this issue is caused by inefficient algorithms. If you see this error multiple times you should try to optimize your code further.

该函数的目标是通过重新排列给定数字的数字来找到给定数字之后的下一个最大数字。例如，如果给我 216，我需要返回 261。

这是我现在的代码:

import itertools

def next_bigger(n):

  # takes a number like 472 and puts it in a list like so: [4, 7, 2]
  num_arr = [int(x) for x in str(n)]
  perms = []
  total = ''

  # x would be a permutation of num_arr, like [7, 2, 4]
  for x in itertools.permutations(num_arr):
    for y in x:
      total += str(y)
    perms.append(int(total))
    total = ''

  # bigger is all permutations that are bigger than n, 
  # so bigger[0] is the next biggest number.
  # if there are no bigger permutations, the function returns -1

  bigger = sorted([x for x in perms if x > n])
  return bigger[0] if bigger else -1

我是 Python 编码的新手，我是否犯了一些错误导致我的代码效率极低？欢迎提出任何建议。

Answer 1

感谢你们给我的所有帮助。我最终从 here 找到了解决方案使用 Next Lexicographical Permutation 算法

这是我提供的解决方案的整理版本 here :

def next_bigger(n):
  # https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/nextperm.py
  # https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

  # Find non-increasing suffix
  arr = [int(x) for x in str(n)]
  i = len(arr) - 1
  while i > 0 and arr[i - 1] >= arr[i]:
    i -= 1
  if i <= 0:
    return -1

  # Find successor to pivot
  j = len(arr) - 1
  while arr[j] <= arr[i - 1]:
    j -= 1
  arr[i - 1], arr[j] = arr[j], arr[i - 1]

  # Reverse suffix
  arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
  return int(''.join(str(x) for x in arr))