如何优化我的函数,它取一个正整数并返回下一个较小的正整数？

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语句来转到下一个数字。时间，但对于nlike )来说仍然很慢，91234567而不是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;
}

有一种非常有效的算法用于计算下一个排列，可以轻松地对其进行修改以获取前一个排列（如果生成的排列以 开头，则返回 -1 0）。我调整了这个算法来做到这一点：

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

Answer 2

该算法可能如下所示：

1. 对于输入数字，查找由和这些数字n中的一些组成的所有数字。例如，如果，我们得到的排序列表为。（例如，JavaScript 中的排列？可以帮助您）。permutationssame digitssortn=213[123, 132, 213, 231, 312, 321]

2. 查找已排序列表中的index i数字。n如果返回else 处i>0的数字（如果它是出现在排序列表的第一个位置的最小数字）。index i-1-1

另一种替代算法可能如下：

递减数字n，直到找到具有完全相同数字的数字（以不同的顺序，您可以对数字进行排序并检查是否相等）。

最有效的方法类似于@Paulpro（https://www.nayuki.io/page/next-lexicographyal-permutation-algorithm）提到的方法

1. longest non-decreasing suffix从 的十进制字符串表示形式中查找n。
2. 如果整个字符串n不减则返回 -1（不能有更小的字符串）。
3. 否则，选择紧邻后缀 as 开头左侧的数字pivot，并将其与that is中的 (the leftmost和 )the largest数字交换。返回这个号码。suffixsmallerpivot