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

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

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

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


当前回答

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

其他回答

下面是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)))))
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<sstream>
#include<iostream>

using namespace std;
int compare (const void * a, const void * b)
{
    return *(char*)a-*(char*)b;
}

/*-----------------------------------------------*/

int main()
{
    char number[200],temp;
    cout<<"please enter your number?"<<endl;
    gets(number);
    int n=strlen(number),length;
    length=n;
    while(--n>0)
    {
        if(number[n-1]<number[n])
        {
            for(int i=length-1;i>=n;i--)
            {
                if(number[i]>number[n-1])
                {
                    temp=number[i];
                    number[i]=number[n-1];
                    number[n-1]=temp;
                    break;
                }
            }
            qsort(number+n,length-n,sizeof(char),compare);
            puts(number); 
            return 0;
        }
    }
    cout<<"sorry itz the greatest one :)"<<endl;
}

如果你用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;
}

这是我的代码,它是这个例子的修改版本

库:

class NumPermExample
{
    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s, ArrayList<String> perm)
    {
        perm1("", s);
    }

    private static void perm1(String prefix, String s, ArrayList<String> perm)
    {
        int N = s.length();
        if (N == 0)
        {
            System.out.println(prefix);
            perm.add(prefix);
        }
        else
        {
            for (int i = 0; i < N; i++)
                perm1(prefix + s.charAt(i), s.substring(0, i)
                    + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s, ArrayList<String> perm)
    {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n, ArrayList<String> perm)
    {
        if (n == 1)
        {
            System.out.println(a);
            perm.add(new String(a));
            return;
        }

        for (int i = 0; i < n; i++)
        {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j)
    {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

    // next higher permutation
    public static int nextPermutation (int number)
    {
        ArrayList<String> perm = new ArrayList<String>();

        String cur = ""+number;

        int nextPerm = 0;

        perm1(cur, perm);

        for (String s : perm)
        {
            if (Integer.parseInt(s) > number
                        && (nextPerm == 0 ||
                            Integer.parseInt(s) < nextPerm))
            {
                nextPerm = Integer.parseInt(s);
            }
        }

            return nextPerm;
    }
}

测试:

public static void main(String[] args) 
{
    int a = 38276;

    int b = NumPermExample.nextPermutation(a);

    System.out.println("a: "+a+", b: "+b);
}

这是另一个Java实现,可以开箱即用,并通过测试完成。 这个解决方案是O(n)个空间和时间,使用老式的动态规划。

如果你想用蛮力,有两种蛮力:

排列所有的东西,然后选择最小值更高的:O(n!) 与此实现类似,但不是DP,而是强制填充的步骤 indexToIndexOfNextSmallerLeft映射将在O(n²)中运行。


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NextHigherSameDigits {

    public long next(final long num) {
        final char[] chars = String.valueOf(num).toCharArray();
        final int[] digits = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            digits[i] = Character.getNumericValue(chars[i]);
        }

        final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>();
        indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null);
        for (int i = 2; i < digits.length; i++) {
            final int left = digits[i - 1];
            final int current = digits[i];
            Integer indexOfNextSmallerLeft = null;
            if (current > left) {
                indexOfNextSmallerLeft = i - 1;
            } else {
                final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1);
                final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null : 
                    digits[indexOfnextSmallerLeftOfLeft];

                if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) {
                    indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft;
                } else {
                    indexOfNextSmallerLeft = null;
                }
            }

            indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft);
        }

        Integer maxOfindexOfNextSmallerLeft = null;
        Integer indexOfMinToSwapWithNextSmallerLeft = null;
        for (int i = digits.length - 1; i >= 1; i--) {
            final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i);
            if (maxOfindexOfNextSmallerLeft == null ||
                    (indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) {

                maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft;
                if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null || 
                        digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) {

                    indexOfMinToSwapWithNextSmallerLeft = i;
                }
            }
        }

        if (maxOfindexOfNextSmallerLeft == null) {
            return -1;
        } else {
            swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft);
            reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1);
            return backToLong(digits);
        }
    }

    private void reverseRemainingOfArray(final int[] digits, final int startIndex) {
        final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length);
        for (int i = tail.length - 1; i >= 0; i--) {
            digits[(digits.length - 1)  - i] = tail[i];                 
        }
    }

    private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) {
        int temp = digits[currentIndex];
        digits[currentIndex] = digits[indexOfNextSmallerLeft];
        digits[indexOfNextSmallerLeft] = temp;
    }

    private long backToLong(int[] digits) {     
        StringBuilder sb = new StringBuilder();
        for (long i : digits) {
            sb.append(String.valueOf(i));
        }

        return Long.parseLong(sb.toString());
    }

    @Test
    public void test() {
        final long input1 =    34722641;
        final long expected1 = 34724126;
        final long output1 = new NextHigherSameDigits().next(input1);
        assertEquals(expected1, output1);

        final long input2 =    38276;
        final long expected2 = 38627;
        final long output2 = new NextHigherSameDigits().next(input2);
        assertEquals(expected2, output2);

        final long input3 =    54321;
        final long expected3 = -1;
        final long output3 = new NextHigherSameDigits().next(input3);
        assertEquals(expected3, output3);

        final long input4 =    123456784987654321L;
        final long expected4 = 123456785123446789L;
        final long output4 = new NextHigherSameDigits().next(input4);
        assertEquals(expected4, output4);

        final long input5 =    9999;
        final long expected5 = -1;
        final long output5 = new NextHigherSameDigits().next(input5);
        assertEquals(expected5, output5);
    }

}