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

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

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

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


当前回答

你的想法

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

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

1234675
    ^

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

1234756

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

其他回答

取一个数,把它分成几位数。如果我们有一个5位数,我们就有5位数:abcde

现在交换d和e,并与原来的数字进行比较,如果它更大,你就得到了答案。

如果它不是很大,交换e和c。现在比较,如果它更小,再次交换d和e(注意递归),取最小的。

一直算下去,直到找到一个更大的数字。通过递归,它应该相当于9行方案,或20行c#。

解决方案(在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));
}

@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;
};
 private static int GetNextHigherNumber(int num)
        {
            //given 38276 return 38627

            string numberstring = num.ToString();

            char[] sNum = numberstring.ToCharArray();

            for (int i = sNum.Length - 1; i > 0; i--)
            {
                for (int j = i - 1; j > 0; j--)
                {
                    if (sNum[i] > sNum[j])
                    {
                        for (int x = i; x > j; x--)
                        {
                            char chr = sNum[x]; 
                            sNum[x] = sNum[x - 1];
                            sNum[x - 1] = chr;
                        }

                        i = 0;
                        break;
                    }
                }
            }

            numberstring = string.Empty;
            for(int x= 0 ; x<sNum.Length;x++)
            {
                numberstring += sNum[x].ToString();
            }

            return Convert.ToInt32(numberstring);
        }

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

库:

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);
}