找最小不重复数的Kotlin算法

【出自BD笔试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定任意一个正整数，求比这个数大且最小的“不重复数”。“不重复数”的含义是相邻两位不相同，例如1101是重复数，而1201是不重复数。

分析与解答：

方法一：蛮力法

最容易想到的方法就是对这个给定的数加1，然后判断这个数是不是“不重复数”，如果不是，则继续加1，直到找到“不重复数”为止。显然这种方法的效率非常低。

方法二：从右到左的贪心法

例如给定数字11099，首先对这个数字加1，变为11000，接着从右向左找出第一对重复的数字00，对这个数字加1，变为11001，继续从右向左找出下一对重复的数00，将其加1，同时把这一位往后的数字变为0101…串（当某个数字自增后，只有把后面的数字变成0101…，才是最小的不重复数字），这个数字变为11010，接着采用同样的方法，11010-＞12010就可以得到满足条件的数。

需要特别注意的是，当对第i个数进行加1操作后可能会导致第i个数与第i+1个数相等，因此，需要处理这种特殊情况，下图以99020为例介绍处理方法。

（1）把数字加1并转换为字符串。

（2）从右到左找到第一组重复的数99（数组下标为i=2），然后把99加1，变为100，然后把后面的字符变为0101…串。得到100010。

（3）由于执行步骤（2）后对下标为2的值进行了修改，导致它与下标为i=3的值相同，因此，需要对i自增变为i=3，接着从i=3开始从右向左找出下一组重复的数字00，对00加1变为01，后面的字符变为0101…串，得到100101。

（4）由于下标为i=3与i+1=4的值不同，因此，可以从i-1=2的位置开始从右向左找出下一组重复的数字00，对其加1就可以得到满足条件的最小的“不重复数”。

根据这个思路给出实现方法如下：

1）对给定的数加1。(www.xing528.com)

2）循环执行如下操作：对给定的数从右向左找出第一对重复的数（下标为i），对这个数字加1，然后把这个数字后面的数变为0101…得到新的数。如果操作结束后下标为i的值等于下标为i+1的值，则对i进行自增，否则对i进行自减；然后从下标为i开始从右向左重复执行步骤2），直到这个数是“不重复数”为止。

实现代码如下：

程序的运行结果如下：

循环次数为：7

23401

循环次数为：11

1201010

循环次数为：13

101010

循环次数为：10

9010

方法三：从左到右的贪心法

与方法二类似，只不过是从左到右开始遍历，如果碰到重复的数字，则把其加1，后面的数字变成0101…串。实现代码如下：

显然，方法三循环的次数少于方法二，因此，方法三的性能要优于方法二。