我正在尝试编写一个函数,它接受一个正整数并返回包含相同数字的下一个较小的正整数,如果没有包含相同数字的较小数字则返回 -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;
}
}
最佳答案
您的代码可以稍微优化一下,例如,您可以在内部循环中使用 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('');
}
关于javascript - 如何优化接受正整数并返回下一个较小正整数的函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42017283/