方法一:蛮力法 最容易想到的方法就是对这个给定的数加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。
2)循环执行如下操作:对给定的数从右向左找出第一对重复的数(下标为i),对这个数字加1,然后把这个数字后面的数变为0101…,得到新的数。如果操作结束后下标为i的值等于下标为i+1的值,则对i进行自增,否则对i进行自减;然后从下标为i开始从右向左重复执行本步骤,直到这个数是“不重复数”为止。
实现代码如下:
public class Test
{
//
//方法功能: 处理数字相加的进位
//输入参数: num为字符数组, pos为进行加1操作对应的下标位置
//
private static void Carry(char[] num, int pos)
{
for(;pos>0;pos--)
{
if(num[pos]>'9')
{
num[pos]='0';
num[pos-1]++;
}
}
}
//
//方法功能: 获取大于n的最小不重复数
//输入参数: n为正整数
//返回值: 大于n的最小不重复数
//
public static int FindMinNonDupNum(int n)
{
int count=0;//用来记录循环次数
char[] nChar=(n+1).ToString().ToCharArray();
char[] ch=new char[nChar.Length+2];
ch[0]='0';
ch[ch.Length-1]='0';
for(int it=0;it<nChar.Length; it++)
ch[it+1]=nChar[it];
int len=ch.Length;
int i=len-2;//从右向左遍历
while(i>0)
{
count++;
if(ch[i-1]==ch[i])
{
ch[i]++; //末尾数字加1
Carry(ch,i); //处理进位
//把下标为i后面的字符串变为0101...
for(intj=i+1;j<len;j++)
{
if((j-i)%2==1)
ch[j]='0';
else
ch[i]='1';
}
//第i位加1后, 可能会与第i+1位相等, i++用来处理这种情况
i++;
}
else
{
i--;
}
}
Console.WriteLine("循环次数为:"+count);
return Convert.ToInt32(new String(ch));
}
public static void main(String[] args)
{
Console.WriteLine(FindMinNonDupNum(23345));
Console.WriteLine(FindMinNonDupNum(1101010));
Console.WriteLine(FindMinNonDupNum(99010));
Console.WriteLine(FindMinN onDupNum(8989));
}
}
程序的运行结果为
循环次数为:7
23401
循环次数为:11
1201010
循环次数为:13
101010
循环次数为:10
9010
方法三:从左到右的贪心法 与方法二类似,只不过是从左到右开始遍历,如果碰到重复的数字,则把其加1,后丽的数字变成0101…。实现代码如下:
public class Test
{
//
//方法功能: 处理数字相加的进位
//输入参数: num为字符数组, pos为进行加1操作对应的下标位置
//
private static void carry(char[] num, int pos)
{
for(;pos>0;pos--)
{
if(num[pos]>'9')
{
num[pos]='0';
num[pos-1]++;
}
}
}
//
//方法功能: 获取大于n的最小不重复数
//输入参数: n为正整数
//返回值: 大于n的最小不重复数
//
public static int findMinNonDupNum(int n)
{
int count=0;//用来记录循环次数
char[] nChar=Integer.valueOf(n+1).toString().toCharArray();
char[] ch=new char[nChar.length+1];
ch[0]='0';
for(int i=0;j<nChar.length; i++)
ch[i+1]=nChar[i];
int len=ch.length;
int i=2; //从左向右遍历
while(i<len)
{
count++;
if(ch[i-1]==ch[i])
{
ch[i]++; //末尾数字加1
carry(ch,i); //处理进位
//把下标为i后面的字符串变为0101…
for(int j=i+1;j<len; j++)
{
if((j-i)%2==1)
ch[j]='0';
else
ch[j]='1';
}
}
else
{
i++;
}
}
System.out.println("循环次数为: "+count);
return Integer.valueOf(new String(ch));
}
}
显然,方法三循环的次数少于方法二,因此方法三的性能优于方法二。