输出下一个更大的数字（一道Python题），求，指，点

Question

注意，请审清题

n = 263457394695时，你的结果可能是997665544332但应该等于263457394956。
因为997665544332 > 263457394956 所以它不是下一个更大的数字

创建一个函数，它接受一个正整数并返回可以通过重新排列其数字形成的下一个更大的数字。
如果无法重新排列数字以形成更大的数字，则返回-1

69980 ==> 80699
483385 ==> 483538
37199563979153 ==> 37199563979315
2017 ==> 2071
9 ==> -1
111 ==> -1
531 ==> -1

自己写了一个，但是不符合题意

def next_bigger(n):
    res = int(''.join(sorted(list(str(n)),reverse=True)))
    return res if res != n else -1

Answer 1

这其实是一道数学题。


做一个简单的说明，在我下面的描述中，数字指0-9中的某一位数字，数指某一个整数，[1234568]用来表示由[]中数字组成的无序的可重复数字集合。


因为需要找到一个刚刚比原数大一点的数字排列，越低位的变化，数增加得越小。如果低4位的重新排列可以生成比原数x大的数y，那么y一定比低5位的重新排列生成的数z更接近数x，这是显而易见的，所以我们应该从右往左进行分析。
所以我们可以得到规则0：能使用低位重排生成的更大的数，就不要使用高位上的数字参与重新排列


我们看一个由[1234568]组成的数，当他们降序排列时形成的数最大如9654321，当他们升序排列时形成的数最小如1234569
我们可以以此得到规则1：当所有数字完全按照降序排列时得到的数最大，反之，升序排列最小。


考虑4531862这个数，我们可以把它划分成4531 862，由上述观点可以知道862是[268]排列成数的最大写法了，如果想让它变大，必须要有高位的数字加入重新排列的步骤，所以把数重新划分为453 1862，1862就存在比它更大的数。而且，因为规则0，我们可以得出结论：从右往左按照升序排列，找到第一个违背升序的数，从这个数的位置向右进行重排列，就能得到比原数更大更接近的数。
这是规则2：将数字从右向左升序划分，直到找到第一个数字打破这种升序关系，则原数的下一个更大值一定是且只是从该位数字右侧的重新排列。


现在问题转换成了一个更简单的子问题，对于一个形如x[abc]（x>a,[abc]为一组数字的降序排列）的数，求该数的下一个更大值。首先，根据规则2，x的位置一定会被替换为[abc]中某一个数字，而且因为是更大值，所以必须要从[abc]中找到一个比x大的数字（因为x>a，所以这个数一定存在），但要求是下一个更大值，也就是说我们要从[abc]里找到一个最接近x的数字，把该数字移动到x的位置。
所以有规则3：将规则2得到的数字替换为它右侧最接近它的数字，剩下数字需要重新排列。


规则3得到的数一定是大于原数的，所以我们现在需要最接近原数的下一个更大值，相当于转换为求需要重新排列的数字排列出的最小的数。又根据规则1，即将这些数字升序排列。
这是最后的规则4：将规则3剩下的数字升序排列。


完成规则4，就找到了输入数的下一个更大的数。我们将所有规则放在一起，基本上就是一个算法了：
规则0：能使用低位重排生成的更大的数，就不要使用高位上的数字参与重新排列
规则1：当所有数字完全按照降序排列时得到的数最大，反之，升序排列最小。
规则2：将数字从右向左升序划分，直到找到第一个数字打破这种升序关系，则原数的下一个更大值一定是且只是从该位数字右侧的重新排列。
规则3：将规则2得到的数字替换为它右侧最接近它的数字，剩下数字需要重新排列。
规则4：将规则3剩下的数字升序排列。

def next_bigger(n):
    num_list = [int(i) for i in str(n)]
    # 将index设置为倒数第二个数字的下标
    index = len(num_list) - 2
    while(index >=  0):
        # 从右到左找到第一个打破升序的数字
        if (num_list[index] < num_list[index+1]):
            # 找到该数字右侧最接近它的数字
            min_close = min([num for num in num_list[index+1:] if num-num_list[index]>0])
            # 找到上一个数字的下标
            exchange_index = index+1+num_list[index+1:].index(min_close)
            # 交换两个数字的位置
            num_list[index],num_list[exchange_index]=num_list[exchange_index],num_list[index]
            # 将剩下的数字升序排列
            new_list = num_list[index+1:]
            new_list.sort()
            # 返回拼接后的整个数
            num_list = num_list[0:index+1]+new_list
            return int("".join([str(i) for i in num_list]))
        index-=1
    return -1

上述方法是比较高效的算法，其实也可以简单粗暴点，全排列+排序，性能上差不少，但好想好写，代码如下：

import itertools
def next_bigger(n):
    # 利用库函数将所有数字的全排列生成一个list，最后转换为数字
    num_list = [int("".join(string)) for string in  set(itertools.permutations(str(n)))]
    # 将列表升序排列
    num_list.sort()
    # 得到传入数n在升序全排列中的下标
    index = num_list.index(n)
    # 返回n在全排列列表的下一个值（数组越界就返回-1）
    return num_list[index+1] if index < len(num_list)-1 else -1