一道整数求值作业_.NET_编程开发_程序员俱乐部

题目描述：给定一个整数 X，找到组成的数字和 X 完全相同的，且大于 X 的最小的那个数。

• 输入要求

    一个整数 X，不会以0开头。

• 输出要求

    输出与 X 数字组成完全相同，且大于 X 的最小的数。若不存在这样的数，输出 0

• 例如，输入 156 输出 165，或者 27711 就是 71127，330 的话就是 0

思路：题目有三大约束：a. 组成与 X 相同  b. 大于 X  c. 最小

针对 a，可以交换 X 的各个位；对于 b，变动的最高位必须比原来大；对于 c，变动的最高位越接近个位越好

1. 暴力法

穷举所有可能的数，然后在大于 X 的里面找最小

2. 反向扫描

从个位开始逆向遍历，向后扫描，找出比自己大的所有位，选择其中最小的，交换之，然后排序，done

如字符串 s="263861"，序号为 0～5
s[4] = 6，后面没有比自己大的
s[3] = 8，同上
s[2] = 3，后面比自己大但最小的数是 6，交换 s[2]和s[4]
从小到大排序 s[3]~s[5]   [注]：因为当前字符后的序列总是降序的，且交换后仍可保持降序，充分利用这一点能有效提高算法效率。故此处无需排序。
所以，最终结果为 266138

实现：

class="brush:python;gutter:true;">#!/usr/bin/env python
#coding=utf8

def test(num):
    text = str(num)
    rtext = list(text[::-1]) #反转字符串以方便遍历
    for i in xrange(1, len(rtext)):
        if rtext[i] < rtext[i-1]: #减少无效比较次数
            gts = [x for x in rtext[:i] if x > rtext[i]] #找到比自己大的所有位
            j = rtext.index(min(gts)) #选择其中最小的
            rtext[i], rtext[j] = rtext[j], rtext[i] #交换之
            return ''.join(rtext[i:][::-1] + rtext[:i])
    return '0'

if __name__ == "__main__":
    from timeit import Timer
    num = input("Input a number: ")
    t1 = Timer("test(num)", "from __main__ import test, num")
    print t1.timeit(1000) #运行1000次所需秒数