鱼C论坛Python精英挑战赛（第四季03期）

凌九霄

import random
import timeit

# 生成一个十万位的随机整数
test = [random.randint(0, 9) for x in range(1, 100001)]
testint = int(''.join(map(str, test)))

'''解题思路：不管多长的整数，都从整数末尾开始检查相邻两个数的大小，当第一次检查到当前数字大于前一位数字时，以前一位数为界，将整数截
  为A,B两段，只需要考虑B段，实际将问题简化为类似 XXXXXXX243 的情况，即最高位需要用与其差值最小的数来作为最高位，其余数按从小到大排
  序，和新的最高位组合成新的数，然后再用先前的A段+B段得到最终答案。
  另外要说明的是，其实十万位什么的只是噱头，并没有实际意义，因为，如果不是刻意，而是随机产生的整数的话，那么99%的情况，99990或更多
  位的整数会被分到不用处理的A段，真正要处理的只是B段那一个小小的数。如果是刻意，那么B段就是形如 X987654321 或者 99999999999 类似的
  数，这样的B段数可能会很大，但是B段处理也依然是简单的'''

def next_int(num):
    numstring = str(num)
    lennum = len(numstring)
    for i in range(lennum - 1, 0, -1):
        if int(numstring[i]) > int(numstring[i - 1]):
            aSection = numstring[:i - 1]
            bSection = numstring[i - 1:]

            tmpnum = bSection[0] #获取B段最高位数字
            tmpSection = sorted(''.join(set(bSection))) #去重后排序
            firstNum = tmpSection[tmpSection.index(tmpnum) + 1]  #排序后得到差值最小的数作为最高位
            bSection = list(bSection)
            bSection.sort()
            bSection.remove(firstNum) #移除已作为最高位的数字

            return int(aSection + firstNum + ''.join(bSection))
        elif i == 1:
            return None


print('十万位数据用时：{0}s'.format(timeit.timeit('next_int(testint)', setup='from __main__ import next_int,testint', number=1)))