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

给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627

我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。

面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。


当前回答

解决方案(在Java中)可能是以下(我相信这里的朋友可以找到更好的): 从字符串的末尾开始交换数字,直到得到一个更高的数字。 也就是说,首先从下位开始移动。然后到达下一个更高的地方,直到你到达下一个更高的地方。 然后对剩下的进行排序。 在你的例子中,你会得到:

38276 --> 38267 (smaller) --> 38627 Found it    
    ^        ^                  ^        

 public static int nextDigit(int number){
    String num = String.valueOf(number);        
    int stop = 0;       
    char [] chars = null;
    outer:
        for(int i = num.length() - 1; i > 0; i--){          
            chars = num.toCharArray();
            for(int j = i; j > 0; j--){
                char temp = chars[j];
                chars[j] = chars[j - 1];
                chars[j - 1] = temp;
                if(Integer.valueOf(new String(chars)) > number){
                    stop = j;                   
                    break outer;                                
                }               
            }               
        }

    Arrays.sort(chars, stop, chars.length); 
    return Integer.valueOf(new String(chars));
}

其他回答

int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
    scanf("%d",&num[i]);   
}
for(int i=0;i<t;i++){
    k=(((num[i]-1)/3)+1); 
    if(k<0)
        printf("-1");
    else if(num[i]<3 || num[i]==4 || num[i]==7)
        printf("-1");
    else{
        num3=3*(2*num[i] - 5*k);
        num5=5*(3*k -num[i]);
        for(int j=0;j<num3;j++)
            printf("5");
        for(int j=0;j<num5;j++)
            printf("3");
    }
    printf("\n");
}

只是使用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

下面是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)))))

你的想法

我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。

其实还不错。您不仅要考虑最后一位数字,还要考虑所有比当前考虑的不那么重要的数字。在此之前,我们有一个单调的数字序列,即最右边的数字比它右边的邻居小。把

1234675
    ^

下一个有相同数字的大数是

1234756

将找到的数字交换为最后一位数字(考虑的数字中最小的数字),其余数字按递增顺序排列。

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