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

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

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

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


当前回答

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

其他回答

@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;
};
function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}

我很确定你的面试官是想委婉地让你说出这样的话:

local number = 564321;

function split(str)
    local t = {};
    for i = 1, string.len(str) do
        table.insert(t, str.sub(str,i,i));
    end
    return t;
end

local res = number;
local i = 1;
while number >= res do
    local t = split(tostring(res));
    if i == 1 then
        i = #t;
    end
    t[i], t[i-1] = t[i-1], t[i];
    i = i - 1;
    res = tonumber(table.concat(t));
end

print(res);

不一定是最有效或最优雅的解决方案,但它在两个循环中解决了所提供的示例,并像他建议的那样一次交换一个数字。

你的想法

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

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

1234675
    ^

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

1234756

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

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

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

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

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