我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
private static int GetNextHigherNumber(int num)
{
//given 38276 return 38627
string numberstring = num.ToString();
char[] sNum = numberstring.ToCharArray();
for (int i = sNum.Length - 1; i > 0; i--)
{
for (int j = i - 1; j > 0; j--)
{
if (sNum[i] > sNum[j])
{
for (int x = i; x > j; x--)
{
char chr = sNum[x];
sNum[x] = sNum[x - 1];
sNum[x - 1] = chr;
}
i = 0;
break;
}
}
}
numberstring = string.Empty;
for(int x= 0 ; x<sNum.Length;x++)
{
numberstring += sNum[x].ToString();
}
return Convert.ToInt32(numberstring);
}
其他回答
下面是Python中的一个紧凑(但部分是蛮力)解决方案
def findnext(ii): return min(v for v in (int("".join(x)) for x in
itertools.permutations(str(ii))) if v>ii)
在c++中，你可以这样排列:https://stackoverflow.com/a/9243091/1149664(它与itertools中的算法相同)
以下是Weeble和BlueRaja描述的顶部答案的实现(其他答案)。我怀疑还有什么更好的办法。
def findnext(ii):
iis=list(map(int,str(ii)))
for i in reversed(range(len(iis))):
if i == 0: return ii
if iis[i] > iis[i-1] :
break
left,right=iis[:i],iis[i:]
for k in reversed(range(len(right))):
if right[k]>left[-1]:
right[k],left[-1]=left[-1],right[k]
break
return int("".join(map(str,(left+sorted(right)))))
PHP实现
时间复杂度O(n)
$n = "9875";
$n_size = strlen($n);
for($i = $n_size-1; $i > 0; $i-- ) {
if($n[$i] > $n[$i-1]){
$temp = $n[$i];
$n[$i] = $n[$i-1];
$n[$i-1] = $temp;
break;
}
}
if($i == 0){
echo "Next Greater value no possible";
}else{
echo $n;
}
int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
scanf("%d",&num[i]);
}
for(int i=0;i<t;i++){
k=(((num[i]-1)/3)+1);
if(k<0)
printf("-1");
else if(num[i]<3 || num[i]==4 || num[i]==7)
printf("-1");
else{
num3=3*(2*num[i] - 5*k);
num5=5*(3*k -num[i]);
for(int j=0;j<num3;j++)
printf("5");
for(int j=0;j<num5;j++)
printf("3");
}
printf("\n");
}
一个几乎相同的问题出现了Code Jam问题，这里有一个解决方案:
http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1
下面用一个例子总结一下这个方法:
34722641
A.将数字序列分成两部分，使右边的部分尽可能长，同时保持递减顺序:
34722 641
(如果整个数字是递减的，就没有比这个数字更大的数字了。)
在这一点上，你知道没有从左边开始的更大的数了，因为右边的剩余数字已经尽可能大了。
责任。选择第一个序列的最后一位:
3472(2) 641
B.2。找出第二个序列中比它大的最小的数字:
3472(2) 6(4)1
你要做的就是找到左边可能的最小增量。
B.3。交换:
3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621
C.将第二个序列按递增顺序排序:
34724 126
d .完成了!
34724126
你把这个数字分开，这样你就知道没有更大的数字具有相同的左边部分，你把左边部分增加了尽可能小的量，你让剩下的右边部分尽可能小，所以你可以确保这个新数字是用相同的数字集合可以得到的最小的更大的数字。
这里有一个我在c#中没有想到的聪明的解决方案
using System;
using System.Linq;
public static long NextBiggerNumber(long n)
{
String str = GetNumbers(n);
for (long i = n+1; i <= long.Parse(str); i++)
{
if(GetNumbers(n)==GetNumbers(i))
{
return i;
}
}
return -1;
}
public static string GetNumbers(long number)
{
return string.Join("", number.ToString().ToCharArray().OrderByDescending(x => x));
}
