给定 int 时下一个更大的数字

Question

当给定一个整数时，我无法优化我的算法以找到具有相同数字的下一个最大数字，如果没有更大的数字则返回 -1。

函数应该做什么的例子：

next_bigger(13): ---> 31

next_bigger(201): ---> 210

next_bigger（2017）：----> 2071

next_bigger(10) -----> -1

next_bigger(587) -----> 758

我认为使用 itertools.permutations() 是解决这个问题的最佳选择，但时间复杂度要求很高。

到目前为止，这是我的代码：

import itertools

def next_bigger(n):
    x = list(itertools.permutations(str(n), len(str(n))))
    lst = [int(''.join(x[i])) for i in range(0, len(x))]
    lst.sort(reverse=True)
    if n == lst[0]:
        return -1
    for i in range(0, len(lst)):
        if lst[i + 1] == n:
            return lst[i]

我尝试将列表包装在一个集合中，然后返回到列表中以删除重复项，但这没有帮助。我还在列表理解中尝试了一个 if 语句，其中列表只包含大于原始数字“n”的值。

Answer 1

我认为这里不需要排列。你需要重新思考/重新制定任务。

如果你需要找到下一个更大的数字，这仅仅意味着当从右到左迭代时，你需要交换左边的第一对< right and the right is the minimum one from all satisfying the condition (so we get next possible number). If there are no such pair then you return

-1

。来自“左一< right..." rule you can deduct that actual right that you will want to swap (if any) is always the most right element:

def next_bigger(n):
    max = '0'
    reversed = list(str(n))[::-1] # reverse the string

    for idx, c in enumerate(reversed):
        if max <= c:
            max = c
            continue
        else:
            # found the place
            reversed[0], reversed[idx] = reversed[idx], reversed[0] # swap the elements
            return int(''.join(reversed[::-1])) # build the number back

    return -1

Answer 2

我不知道为什么

itertools.permutations

甚至存在。自己编写代码很容易，但效率低得离谱，以致于任何人为了获得比玩具示例更多的代码几乎总是会犯错误。正如你所发现的。

你所要做的就是思考下一个数字的模式。为此，我们需要两个事实：

1. 我们想通过移动一个较小的数字来尽可能地增加最小的数字
2. 后面的数字应该按升序排列。

所以带上你的

587

。我们不能将任何东西移入 1 的数字。移动到 10 位的 7 会更小。我们可以移动到 100 位的最小的东西是

7

。之后其他数字按升序排列，所以

58

。给我们

758

.

所以我们要做的是从最后一位到第一位，在我们进行的过程中按升序对末尾进行排序，直到我们发现我们可以使数字更大。当我们这样做时，我们会找到最小的东西放进去。

def next_bigger (n):
    # array manipulation is easier with arrays
    digits = list(str(n))
    # i is the position of the digit we're working on.
    # This places it on the 10s digit
    i = len(digits) - 2
    # While i is still in the digits.
    while 0 <= i:
        # We have found the digit to increase!
        if digits[i] < digits[-1]:
            # j will be the digit to exchange with.
            j = len(digits) - 1
            # Scan backwards until we find the smallest digit to place at i
            while digits[i] < digits[j-1]:
                j -= 1
            # swap
            (digits[i], digits[j]) = (digits[j], digits[i])
            # turn it back into a number and return it.
            return int(''.join(digits))
        else:
            # Move the `i`'th digit to the end.
            d = digits.pop(i)
            digits.append(d)
            # And now we'll look at the next largest digit.
            i -= 1
    # We failed to find larger.
    return -1

# Here are all of your test cases.   
for n in [13, 201, 2017, 10, 785]:
    print(n, next_bigger(n))

Answer 3

接受的答案解释了方法是什么。我在这里提供了一个实现，当要增加的数字被识别时停止显式迭代，并通过对后面的数字进行排序（使用

sorted

）来重建结果字符串：

def next_bigger(n):
    s = str(n)
    for i in range(len(s) - 2, -1, -1):
        if s[i] < s[i + 1]:
            for k in range(len(s) - 1, i, -1):
                if s[i] < s[k]:
                    return int(s[:i] + s[k] + "".join(sorted(s[i:k] + s[k+1:])))
    return -1