我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
只是使用python的另一个解决方案:
def PermutationStep(num):
if sorted(list(str(num)), reverse=True) == list(str(num)):
return -1
ls = list(str(num))
n = 0
inx = 0
for ind, i in enumerate(ls[::-1]):
if i < n:
n = i
inx = -(ind + 1)
break
n = i
ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]
nl = ls[inx::-1][::-1]
ln = sorted(ls[inx+1:])
return ''.join(nl) + ''.join(ln)
print PermutationStep(23514)
输出:
23541
其他回答
一个几乎相同的问题出现了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
你把这个数字分开，这样你就知道没有更大的数字具有相同的左边部分，你把左边部分增加了尽可能小的量，你让剩下的右边部分尽可能小，所以你可以确保这个新数字是用相同的数字集合可以得到的最小的更大的数字。
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;
}
我很确定你的面试官是想委婉地让你说出这样的话:
local number = 564321;
function split(str)
local t = {};
for i = 1, string.len(str) do
table.insert(t, str.sub(str,i,i));
end
return t;
end
local res = number;
local i = 1;
while number >= res do
local t = split(tostring(res));
if i == 1 then
i = #t;
end
t[i], t[i-1] = t[i-1], t[i];
i = i - 1;
res = tonumber(table.concat(t));
end
print(res);
不一定是最有效或最优雅的解决方案，但它在两个循环中解决了所提供的示例，并像他建议的那样一次交换一个数字。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
char temp[100],a[100]`enter code here`,n;
min=9999;
//cout<<"Enter the number\n";
cin>>a;
len=strlen(a);
for(i=0;i<len;i++)
{
if(a[i]<a[i+1]){flag=1;break;}
}
if(flag==0){cout<<a<<endl;}
else
{
for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
for(k=0;k<i-1;k++)cout<<a[k];
for(j=i;j<len;j++)
{
if(((int)a[j]-48)-((int)a[i-1]-48)>0)
{
diff=((int)a[j]-48)-((int)a[i-1]-48);
if(diff<min){n=a[j];min=diff;}
}
}
cout<<n;
for(z=i-1;z<len;z++)
{
temp[u]=a[z];
u++;
}
temp[u]='\0';
sort(temp,temp+strlen(temp));
for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
}
return 0;
}
给定n位数字加9。然后检查它是否在限制范围内(第一个(n+1)位数)。如果是，则检查新号码中的数字是否与原号码中的数字相同。 重复加9，直到两个条件都为真。 当数字超过限制时停止算法。
对于这种方法，我想不出一个与之相矛盾的测试用例。
