javascript - How to optimize my function that takes a positive integer and returns the next smaller positive integer? - Stack Ov

admin管理员组

文章数量:1395752

I am trying to write a function that takes a positive integer and returns the next smaller positive integer containing the same digits, and -1 when there is no smaller number that contains the same digits.

For example:

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

I wrote a code that solves this, but I don't really know how to optimize it further. Could you please help me? It runs fairly fast on repl.it, but when I submit it, it says it takes more than 1200ms and doesn't allow me to submit it even though all the tests pass.

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

I am trying to write a function that takes a positive integer and returns the next smaller positive integer containing the same digits, and -1 when there is no smaller number that contains the same digits.

For example:

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

I wrote a code that solves this, but I don't really know how to optimize it further. Could you please help me? It runs fairly fast on repl.it, but when I submit it, it says it takes more than 1200ms and doesn't allow me to submit it even though all the tests pass.

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

• javascript
• string
• algorithm
• math
• numbers

Share Improve this question Follow asked Feb 3, 2017 at 5:19 user7269511user7269511 6

• 4 Perhaps this is more suited in code review – E. Sundin Commented Feb 3, 2017 at 5:22
• Look for patterns to narrow the problem space. For example, you should only be checking permutations of the digits in the input. – castletheperson Commented Feb 3, 2017 at 5:27
• Seems like this is a kata on Codewars – JohanP Commented Feb 3, 2017 at 5:29
• yeah it is a kata on codewars JohanP. thanks E.Sundin, I'll post it there. 4castle, I don't understand what you mean, could you please elaborate? – user7269511 Commented Feb 3, 2017 at 5:30
• It seems the problem is about finding the next lexicographically smaller permutation if you use c++ you can use next_permutation with suitable pare function cplusplus./reference/algorithm/next_permutation or you can implement it yourself. But you may need to handle special case where there are leading zero in the next smaller permutation – Petar Petrovic Commented Feb 3, 2017 at 5:35

 |  Show 1 more ment

2 Answers 2

Sorted by: Reset to default 5

Your code could be optimized a bit, for instance you could use a break statement in your inner loop to move on to the next number as soon as you know the current one isn't going to work (that should make it run in about half the time, but it is still quite slow for an n like 91234567) and instead of n.toString().split("").length in the loop, use a variable so you only need to convert n to an array once.

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

There is a very efficient algorithm for puting the next permutation, which can easily be adapted to get the previous one instead (and return -1 if the resulting permutation starts with 0). I adapted this algorithm to do that:

[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('');
}

The algorithm could be like the following:

1. For the input number n find all numbers that are formed with some permutations of the same digits and sort these numbers. For example, if n=213, we get the sorted list as [123, 132, 213, 231, 312, 321]. (e.g., Permutations in JavaScript? can help you).

2. Find the index i of the number n in the sorted list. If i>0 return the number at index i-1 else return -1 (if it's the smallest number appearing at the first position of the sorted list).

Another alternative algorithm could be the following:

Decrement the number n until and unless you find one that has exactly same digits (in a different order, you can sort the digits and check for equality).

The most efficient will be similar to the one referred to by @Paulpro(https://www.nayuki.io/page/next-lexicographical-permutation-algorithm)

1. Find the longest non-decreasing suffix from the decimal string representation of n.
2. If the entire string n is non-decreasing then return -1 (there can't be any smaller).
3. Otherwise choose the digit immediately left to the start of the suffix as pivot and swap it with (the leftmost and) the largest digit in the suffix that is smaller than the pivot. Return this number.

本文标签：