javascript - 如何优化接受正整数并返回下一个较小正整数的函数？

Question

我正在尝试编写一个函数，它接受一个正整数并返回包含相同数字的下一个较小的正整数，如果没有包含相同数字的较小数字则返回 -1。

For example:

nextSmaller(21) == 12
nextSmaller(531) == 513
nextSmaller(2071) == 2017

我写了一个解决这个问题的代码，但我真的不知道如何进一步优化它。请你帮助我好吗？它在 repl.it 上运行得相当快，但是当我提交它时，它说它需要超过 1200 毫秒并且不允许我提交它，即使所有测试都通过了。

function nextSmaller(n) {
var nArray= n.toString().split("")
var minimumNum = 1 + Array(nArray.length).join('0')
for(var i=n-1; i >= minimumNum; i--) {
  var newNumArray = i.toString().split('');
  var counter = 0;
  for (var j=0; j<newNumArray.length; j++) {
    if (nArray.indexOf(newNumArray[j]) > -1) {
        counter++
        nArray.splice(nArray.indexOf(newNumArray[j]), 1)
        if (counter === n.toString().split("").length) {
        return i;
        }
     } 
  }
       nArray = n.toString().split("");
       if (i === Number(minimumNum)) return -1;
  }
}

Answer 1

您的代码可以稍微优化一下，例如，您可以在内部循环中使用 break 语句，一旦您知道当前的数字将无法工作(应该让它运行大约一半的时间，但对于像 91234567 这样的 n 而不是 n.toString().split("") 来说它仍然很慢。 length 在循环中，使用一个变量，所以你只需要将 n 转换为数组一次。

function nextSmaller(n) {
  var nArray = n.toString().split("")
  var length = nArray.length;
  var minimumNum = 1 + Array(length).join('0')
  for(var i=n-1; i >= minimumNum; i--) {
    var newNumArray = i.toString().split('');
    var counter = 0;
    for (var j=0; j<newNumArray.length; j++) {
      if (nArray.indexOf(newNumArray[j]) < 0)
          break;
      counter++
      nArray.splice(nArray.indexOf(newNumArray[j]), 1)
      if (counter === length) {
          return i;
      }
    }
    nArray = n.toString().split("");
  }
  return -1;
}

有一种计算下一个排列的非常有效的算法，可以很容易地修改它来获取前一个排列(如果生成的排列以 0 开头，则返回 -1)。我改编了 this algorithm 来做到这一点:

[21,531,2071,912345678,9123545678,915345678].forEach( x => console.log( nextSmaller( x ) ) );

function nextSmaller(n) {
  
    const arr = ( n + '' ).split( '' ).map( Number );
  
    // Find longest non-decreasing suffix
    let i, prev = 9;
    for ( i = arr.length; i--; ) {
        if ( arr[ i ] > prev )
            break;
        prev = arr[ i ];
    }
  
    // If whole sequence is non-decreasing,
    // it is already the smallest permutation
    if ( i < 0 )
        return -1;
  
    const pivot_i = i;
    const pivot = arr[ pivot_i ];
  
    for ( i = arr.length; i--; ) {
        if ( arr[ i ] < pivot )
            break;
    }
  
    arr[ pivot_i ] = arr[ i ];
    arr[ i ] = pivot;

    if ( arr[ 0 ] === 0 )
        return -1;
  
    return +arr.slice( 0, pivot_i + 1 ).concat( arr.slice( pivot_i + 1 ).reverse( ) ).join('');
}