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

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

其他回答

关于如何做到这一点,请参阅Knuth的“计算机编程艺术:生成所有排列”(.ps.gz)中的“算法L”。

如果你用c++编程,你可以使用next_permutation:

#include <algorithm>
#include <string>
#include <iostream>

int main(int argc, char **argv) {
  using namespace std; 
   string x;
   while (cin >> x) {
    cout << x << " -> ";
    next_permutation(x.begin(),x.end());
    cout << x << "\n";
  }
  return 0;
}

我只测试了两个数字。他们工作。 在去年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

给定n位数字加9。然后检查它是否在限制范围内(第一个(n+1)位数)。如果是,则检查新号码中的数字是否与原号码中的数字相同。 重复加9,直到两个条件都为真。 当数字超过限制时停止算法。

对于这种方法,我想不出一个与之相矛盾的测试用例。

这里有一个我在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));
    }