给定一个数字，找出下一个与原始数字具有完全相同的数字集的更高的数字

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

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

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

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

当前回答

只是使用python的另一个解决方案:

def PermutationStep(num):
    if sorted(list(str(num)), reverse=True) == list(str(num)):
        return -1
    ls = list(str(num))
    n = 0
    inx = 0
    for ind, i in enumerate(ls[::-1]):
        if i < n:
            n = i
            inx = -(ind + 1)
            break
        n = i
    ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]

    nl = ls[inx::-1][::-1]
    ln = sorted(ls[inx+1:])
    return ''.join(nl) + ''.join(ln)

print PermutationStep(23514)

输出:

2014-01-06 17:35:10

其他回答

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

2015-06-01 12:16:35

PHP代码

function NextHigherNumber($num1){
$num = strval($num1);
$max = 0;
for($i=(strlen($num)-2); $i>=0; $i--){
    $numArrayRaw = substr($num, $i);
    $numArray = str_split($numArrayRaw);
    $max = max($numArray);
    if ($numArray[0] < $max){
        sort( $numArray, SORT_NUMERIC );
        array_pop($numArray);
        $numarrstr = implode("",$numArray);
        $rt = substr($num,0,$i) . $max . $numarrstr;
        return $rt;
    }
}
return "-1";
}
echo NextHigherNumber(123);

2020-02-19 19:29:12

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

2015-06-01 12:35:51

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

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

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

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

2012-02-20 21:16:50

只是使用python的另一个解决方案:

def PermutationStep(num):
    if sorted(list(str(num)), reverse=True) == list(str(num)):
        return -1
    ls = list(str(num))
    n = 0
    inx = 0
    for ind, i in enumerate(ls[::-1]):
        if i < n:
            n = i
            inx = -(ind + 1)
            break
        n = i
    ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]

    nl = ls[inx::-1][::-1]
    ln = sorted(ls[inx+1:])
    return ''.join(nl) + ''.join(ln)

print PermutationStep(23514)

输出:

2014-01-06 17:35:10

给定一个数字，找出下一个与原始数字具有完全相同的数字集的更高的数字

推荐文章

最新文章

标签