我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
取一个数,把它分成几位数。如果我们有一个5位数,我们就有5位数:abcde
现在交换d和e,并与原来的数字进行比较,如果它更大,你就得到了答案。
如果它不是很大,交换e和c。现在比较,如果它更小,再次交换d和e(注意递归),取最小的。
一直算下去,直到找到一个更大的数字。通过递归,它应该相当于9行方案,或20行c#。
其他回答
@BlueRaja算法的javascript实现。
var Bar = function(num){
num = num.toString();
var max = 0;
for(var i=num.length-2; i>0; i--){
var numArray = num.substr(i).split("");
max = Math.max.apply(Math,numArray);
if(numArray[0]<max){
numArray.sort(function(a,b){return a-b;});
numArray.splice(-1);
numArray = numArray.join("");
return Number(num.substr(0,i)+max+numArray);
}
}
return -1;
};
下面是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)))))
我只测试了两个数字。他们工作。 在去年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
I didn't know anything about the brute force algorithm when answering this question, so I approached it from another angle. I decided to search the entire range of possible solutions that this number could possibly be rearranged into, starting from the number_given+1 up to the max number available (999 for a 3 digit number, 9999 for 4 digits, etc.). I did this kind of like finding a palindrome with words, by sorting the numbers of each solution and comparing it to the sorted number given as the parameter. I then simply returned the first solution in the array of solutions, as this would be the next possible value.
下面是我的Ruby代码:
def PermutationStep(num)
a = []
(num.to_s.length).times { a.push("9") }
max_num = a.join('').to_i
verify = num.to_s.split('').sort
matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }
if matches.length < 1
return -1
else
matches[0]
end
end
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);