输出下一个更大的数字(一道Python题)求指点

躲进小宋怀里
  • 11

注意,请审清题

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

题目如下

创建一个函数,它接受一个正整数并返回可以通过重新排列其数字形成的下一个更大的数字。
如果无法重新排列数字以形成更大的数字,则返回-1
实例:
12 ==> 21
513 ==> 531
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
回复
阅读 386
5 个回答
def bigger(num):
    nums = [int(x) for x in list(str(num))]

    # 找到尾部第一个非最大序列
    for i in range(-2, -len(nums), -1)
        if sorted(nums[i:], reverse=True) != nums[i:]:
            break

    # 按找到的位置把原数字串分成left,pos,right3个部分。
    # left不变,right中比pos大的最小值换到pos位置。
    t = nums[i + 1:]
    r = [x for x in t if x > nums[i]][-1] #这里没做错误处理,如果初始数就是最大值会出错
    ret = nums[:i] + [r]
    
    # right把前面替换的值去掉,把pos的值加进来,组成最小排列
    t.remove(r)
    t.append(nums[i])
    t.sort()
    
    # 把处理好的right尾部加上来
    ret = ret + t
    return int("".join([str(x) for x in ret]))


print(bigger(263457394695))

next-permutation原题啊
把数字转成数组,然后用next-permutation算法求出下一个排列,再把数组转回数字就行了

微博上看到了,一看是 Python 就手痒了,就特地来安逸一下。

# from collections import namedtuple
# from typing import List
def find_next_greater(num: int) -> int:
    ns: List[str] = [e for e in str(num)]
    l: int = len(ns)
    Needle = namedtuple('Needle', ['LAST', 'PENULTIMATE'])
    needle: Needle = Needle(LAST=l-1, PENULTIMATE=l-2)
    for i in range(needle.PENULTIMATE, -1, -1):
        for j in range(needle.LAST, i, -1):
            if ns[j] > ns[i]:
                ns[i], ns[j] = ns[j], ns[i]
                ns[i+1:] = sorted(ns[i+1:])
                return int(''.join(ns))
    return -1


find_next_greater(263457394695) == 263457394956  # True
find_next_greater(5446) == 5464  # True
find_next_greater(10006) == 10060  # True
find_next_greater(1000786) == 1000867  # True
find_next_greater(10086) == 10608  # True
find_next_greater(26) == 62  # True
find_next_greater(321) == -1  # True
find_next_greater(3212) == 3221  # True
find_next_greater(8) == -1  # True
find_next_greater(133398999998) == 133399889999  # True

还有待优化:获取所有组合时没有按小到大得到 如果能可以尽早退出

def x(n=263457394695):
    ns = str(n)
    if len(ns) < 3:
        n2 = int("".join(sorted(ns, reverse=1)))
        return n2 if n2 > n else -1
    i = 2
    while i < len(ns):
        ns2 = ns[-i:]
        nslist = permutation([s for s in ns2], 0, set())
        i2 = nslist.index(int(ns2))
        if i2 < len(nslist) - 1:
            return ns[:-i] + str(nslist[i2 + 1])
        i += 1
    return -1


def swap(str, i, j):
    # 交换字符数组下标为i和j对应的字符
    tmp = str[i]
    str[i] = str[j]
    str[j] = tmp


def permutation(str, start, data):
    if start == len(str) - 1:
        # 完成全排列后输出当前排列的字符串
        data.add(int(''.join(str)))
    else:
        i = start
        while i < len(str):
            # 交换start与i所在位置的字符
            swap(str, start, i)
            # 固定第一个字符,对剩余的字符进行全排列
            permutation(str, start + 1, data)
            # 还原start与i所在位置的字符
            swap(str, start, i)
            i += 1
    return sorted(data)


print x(123456)
def next_bigger(n):
    s = list(str(n))
    w = len(s)
    for i in range(w - 2, -1, -1):
        if s[i] < s[i + 1]:
            for j in range(w - 1, i, -1):
                if s[j] > s[i]:
                    s[i], s[j] = s[j], s[i]
                    break
            s[i + 1 :] = sorted(s[i + 1 :])
            return int("".join(s))
    return -1
你知道吗?

宣传栏