我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。

给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定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);