Как оптимизировать мою функцию, которая принимает положительное целое число и возвращает следующее меньшее положительное целое число?

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

алгоритм может быть как следующее:

1. Для ввода числа n найти все числа, которые формируются с некоторым permutations из same digits и sort этих чисел. Например, если n=213, мы получаем отсортированный список как [123, 132, 213, 231, 312, 321]. (например, Permutations in JavaScript? может вам помочь).

2. Найти index i с номером n в отсортированном виде. Если i>0 верните номер на номер index i-1, верните -1 (если это наименьшее число, отображаемое в первой позиции отсортированного списка).

Другой альтернативный алгоритм может быть следующим:

Decrement число n до и если вы не найдете тот, который имеет точно такие же цифры (в другом порядке, вы можете отсортировать цифры и проверить равенство) ,

Наиболее эффективным будет похож на тот ссылается @Paulpro (https://www.nayuki.io/page/next-lexicographical-permutation-algorithm)

1. Найти в longest non-decreasing suffix от десятичной строкового представления n.
2. Если целая строка n не убывает, тогда возврат -1 (их не может быть меньше).
3. В противном случае выберите цифру сразу влево до начала суффикса как pivot и поменять его с (the leftmost и) the largest цифр в suffix, который smaller чем pivot. Верните этот номер.

Answer 2

Ваш код может быть оптимизирован, например, вы можете использовать оператор break в своем внутреннем цикле, чтобы перейти к следующему номеру, как только вы узнаете, что текущий не будет работать (что должно запустите его примерно в половине случаев, но он по-прежнему довольно медленный для n, например 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).Я приспособил 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(''); 
 
}