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

凌九霄

1. import random
   
2. import timeit
   
3. 
   
4. # 生成一个十万位的随机整数
   
5. test = [random.randint(0, 9) for x in range(1, 100001)]
   
6. testint = int(''.join(map(str, test)))
   
7. 
   
8. '''解题思路：不管多长的整数，都从整数末尾开始检查相邻两个数的大小，当第一次检查到当前数字大于前一位数字时，以前一位数为界，将整数截
   
9.   为A,B两段，只需要考虑B段，实际将问题简化为类似 XXXXXXX243 的情况，即最高位需要用与其差值最小的数来作为最高位，其余数按从小到大排
   
10.   序，和新的最高位组合成新的数，然后再用先前的A段+B段得到最终答案。
    
11.   另外要说明的是，其实十万位什么的只是噱头，并没有实际意义，因为，如果不是刻意，而是随机产生的整数的话，那么99%的情况，99990或更多
    
12.   位的整数会被分到不用处理的A段，真正要处理的只是B段那一个小小的数。如果是刻意，那么B段就是形如 X987654321 或者 99999999999 类似的
    
13.   数，这样的B段数可能会很大，但是B段处理也依然是简单的'''
    
14. 
    
15. def next_int(num):
    
16.     numstring = str(num)
    
17.     lennum = len(numstring)
    
18.     for i in range(lennum - 1, 0, -1):
    
19.         if int(numstring[i]) > int(numstring[i - 1]):
    
20.             aSection = numstring[:i - 1]
    
21.             bSection = numstring[i - 1:]
    
22. 
    
23.             tmpnum = bSection[0] #获取B段最高位数字
    
24.             tmpSection = sorted(''.join(set(bSection))) #去重后排序
    
25.             firstNum = tmpSection[tmpSection.index(tmpnum) + 1]  #排序后得到差值最小的数作为最高位
    
26.             bSection = list(bSection)
    
27.             bSection.sort()
    
28.             bSection.remove(firstNum) #移除已作为最高位的数字
    
29. 
    
30.             return int(aSection + firstNum + ''.join(bSection))
    
31.         elif i == 1:
    
32.             return None
    
33. 
    
34. 
    
35. print('十万位数据用时：{0}s'.format(timeit.timeit('next_int(testint)', setup='from __main__ import next_int,testint', number=1)))
    
36. 
    

复制代码