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

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

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

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


当前回答

回答在java与一个更多的条件添加

Next number should also be an Even number public static int nextDigit(int number) { String num = String.valueOf(number); int stop = 0; char[] orig_chars = null; char[] part1 = null; char[] part2 = null; orig_chars = num.toCharArray(); System.out.println("vivek c r"); for (int i = orig_chars.length - 1; i > 0; i--) { String previous = orig_chars[i - 1] + ""; String next = orig_chars[i] + ""; if (Integer.parseInt(previous) < Integer.parseInt(next)) { if (Integer.parseInt(previous) % 2 == 0) { String partString1 = ""; String partString2 = ""; for (int j = 0; j <= i - 1; j++) { partString1 = partString1.concat(orig_chars[j] + ""); } part1 = partString1.toCharArray(); for (int k = i; k < orig_chars.length; k++) { partString2 = partString2.concat(orig_chars[k] + ""); } part2 = partString2.toCharArray(); Arrays.sort(part2); for (int l = 0; l < part2.length; l++) { char temp = '0'; if (part2[l] > part1[i - 1]) { temp = part1[i - 1]; part1[i - 1] = part2[l]; part2[l] = temp; break; } } for (int m = 0; m < part2.length; m++) { char replace = '0'; if (part2[m] % 2 == 0) { replace = part2[m]; for (int n = m; n < part2.length - 1; n++) { part2[n] = part2[n + 1]; } part2[part2.length - 1] = replace; break; } } System.out.print(part1); System.out.println(part2); System.exit(0); } } } System.out.println("NONE"); return 0; }

其他回答

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

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

你的想法

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

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

1234675
    ^

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

1234756

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

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