给定一个数字,找到下一个更高的数字,它与原始数字具有完全相同的数字位数

Question

我只是轰炸了一次采访,并在我的采访问题上取得了很大的进展.任何人都可以让我知道如何做到这一点？我尝试在网上搜索但找不到任何东西:

给定一个数字,找到下一个更高的数字,它与原始数字具有完全相同的数字位数.例如:给出38276返回38627

我想首先找到小于一位数的第一个数字(从右边)的索引.然后我会旋转子集中的最后一个数字,使得它是由相同数字组成的下一个最大数字,但是卡住了.

采访者还建议尝试一次交换一个数字,但我无法弄清楚算法,只是盯着屏幕看了20-30分钟.不用说,我想我将不得不继续寻找工作.

编辑:为了它的价值,我被邀请参加下一轮的采访

Answer 1

你可以这样做O(n)(在哪里n是位数),如下所示:

从右侧开始,您会找到第一对数字,使左数字小于右数字.我们用"digit-x"来表示左边的数字.找到digit-x右侧大于digit-x的最小数字,并将其放在digit-x的左侧.最后,按升序对剩余的数字进行排序 - 因为它们已经按降序排列,所以你需要做的只是反转它们(保存为digit-x,可以放在正确的位置O(n)).

一个例子将使这更清楚:

123456784987654321
start with a number

123456784 987654321
         ^the first place from the right where the left-digit is less than the right  
         Digit "x" is 4

123456784 987654321
              ^find the smallest digit larger than 4 to the right

123456785 4 98764321
        ^place it to the left of 4

123456785 4 12346789
123456785123446789
         ^sort the digits to the right of 5.  Since all of them except 
         the '4' were already in descending order, all we need to do is 
         reverse their order, and find the correct place for the '4'

正确性证明:

让我们用大写字母来定义数字字符串和小写字母.语法AB是指"字符串的连接A和B". <是字典排序,当数字串长度相等时,它与整数排序相同.

我们的原始数字N是形式AxB,其中x是单个数字并按B降序排序.
通过我们的算法发现的数量AyC,其中y ? B最小的数字> x (它必须存在因方式x选择,见上文),并且C将按升序排序.

假设有一些数字(使用相同的数字)N'这样AxB < N' < AyC. N'必须从A它开始,否则它不会落在它们之间,所以我们可以在表单中写它AzD.现在我们的不等式是AxB < AzD < AyC,这相当于xB < zD < yC所有三个数字字符串包含相同数字的位置.

为了实现这一点,我们必须拥有x <= z <= y.由于y是最小的数字> x,z不能是两者之间,所以无论是z = x或z = y.说z = x.然后我们的不平等xB < xD < yC,这意味着B < D其中两个B与D具有相同的数字.然而,B是降序排序,所以是与那些比它更大的数字没有字符串.因此我们不能拥有B < D.按照相同的步骤,我们看到,如果z = y,我们不能拥有D < C.

因此N'不能存在,这意味着我们的算法正确找到下一个最大的数字.

Answer 2

一个几乎完全相同的问题出现了Code Jam问题,并在此处提供了解决方案:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

以下是使用示例的方法摘要:

34722641

A.将数字序列分成两部分,使右部分尽可能长,同时保持递减顺序:

34722 641

(如果整个数字按递减顺序排列,则没有添加数字就没有更大的数字.)

B.1.选择第一个序列的最后一位数字:

3472(2) 641

B.2.找到第二个序列中比它大的最小数字:

3472(2) 6(4)1

B.3.交换它们:

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

C.将第二个序列按递增顺序排序:

34724 126

D.完成!

34724126

Answer 3

这是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)))))

Answer 4

至少,这里有一些基于蛮力的基于String的解决方案,您应该已经能够从头顶出现:

38276排序中的数字列表是23678

38627排序中的数字列表是23678

蛮力增量,排序和比较

沿着蛮力,解决方案将转换为字符串,并使用这些数字强制所有可能的数字.

从中创建所有内容,将它们放入列表并对其进行排序,在目标条目之后获取下一个条目.

如果你花了30分钟,并且至少没有提出至少蛮力的方法,我也不会雇用你.

在商业世界中,一个不优雅,缓慢和笨重但完成工作的解决方案总是比没有解决方案更有价值,事实上几乎描述了所有商业软件,不优雅,缓慢和笨重.

Answer 5

function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}