我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
下面是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代码
function NextHigherNumber($num1){
$num = strval($num1);
$max = 0;
for($i=(strlen($num)-2); $i>=0; $i--){
$numArrayRaw = substr($num, $i);
$numArray = str_split($numArrayRaw);
$max = max($numArray);
if ($numArray[0] < $max){
sort( $numArray, SORT_NUMERIC );
array_pop($numArray);
$numarrstr = implode("",$numArray);
$rt = substr($num,0,$i) . $max . $numarrstr;
return $rt;
}
}
return "-1";
}
echo NextHigherNumber(123);
我很确定你的面试官是想委婉地让你说出这样的话:
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);
不一定是最有效或最优雅的解决方案，但它在两个循环中解决了所提供的示例，并像他建议的那样一次交换一个数字。
至少，这里有几个基于字符串的暴力解决方案的例子，你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量，排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int，把它们放在一个列表中并排序， 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上，却没有想出一个蛮力的方法，我也不会雇用你。
在商业世界中，一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值，事实上，这几乎描述了所有不优雅、缓慢和笨拙的商业软件。
我只测试了两个数字。他们工作。 在去年12月退休之前，我做了8年的IT经理，我关心三件事: 1)准确性:如果它总是有效，那就很好。 2)速度:用户可以接受。 3)明确:我可能没有你聪明，但我付你薪水。确保你用英语解释你在做什么。
奥马尔，祝你好运。
Sub Main()
Dim Base(0 To 9) As Long
Dim Test(0 To 9) As Long
Dim i As Long
Dim j As Long
Dim k As Long
Dim ctr As Long
Const x As Long = 776914648
Dim y As Long
Dim z As Long
Dim flag As Boolean
' Store the digit count for the original number in the Base vector.
For i = 0 To 9
ctr = 0
For j = 1 To Len(CStr(x))
If Mid$(CStr(x), j, 1) = i Then ctr = ctr + 1
Next j
Base(i) = ctr
Next i
' Start comparing from the next highest number.
y = x + 1
Do
' Store the digit count for the each new number in the Test vector.
flag = False
For i = 0 To 9
ctr = 0
For j = 1 To Len(CStr(y))
If Mid$(CStr(y), j, 1) = i Then ctr = ctr + 1
Next j
Test(i) = ctr
Next i
' Compare the digit counts.
For k = 0 To 9
If Test(k) <> Base(k) Then flag = True
Next k
' If no match, INC and repeat.
If flag = True Then
y = y + 1
Erase Test()
Else
z = y ' Match.
End If
Loop Until z > 0
MsgBox (z), , "Solution"
End Sub
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;
}
