Изучение различных подходов к поиску следующего меньшего положительного целого числа с теми же цифрами

В этой статье блога мы углубимся в увлекательную задачу поиска следующего меньшего положительного целого числа, содержащего те же цифры, что и заданное число. Мы рассмотрим различные методы и предоставим примеры кода для демонстрации каждого подхода. Итак, берите свой любимый напиток и начнем!

Метод 1: подход грубой силы
Подход грубой силы включает в себя генерацию всех возможных перестановок цифр заданного числа и поиск следующей меньшей перестановки. Вот пример фрагмента кода на Python:

def find_next_smaller_integer(number):
    digits = list(str(number))
    n = len(digits)

    for i in range(n-1, 0, -1):
        if digits[i] < digits[i-1]:
            for j in range(n-1, i-1, -1):
                if digits[j] < digits[i-1]:
                    digits[i-1], digits[j] = digits[j], digits[i-1]
                    return int(''.join(digits[:i] + sorted(digits[i:], reverse=True)))

    return -1  # No smaller integer found
# Example usage
number = 54321
next_smaller = find_next_smaller_integer(number)
print(f"The next smaller integer containing the same digits as {number} is: {next_smaller}")

Метод 2: сортировка и замена
Другой подход включает сортировку цифр в порядке убывания и замену соседних цифр, чтобы найти следующее меньшее целое число. Вот пример фрагмента кода на JavaScript:

function findNextSmallerInteger(number) {
    let digits = Array.from(String(number), Number);
    let n = digits.length;

    let i = n - 2;
    while (i >= 0 && digits[i] <= digits[i + 1]) {
        i--;
    }

    if (i < 0) {
        return -1;  // No smaller integer found
    }

    let j = n - 1;
    while (j > i && digits[j] >= digits[i]) {
        j--;
    }

    [digits[i], digits[j]] = [digits[j], digits[i]];
    let nextSmaller = parseInt(digits.slice(0, i + 1).concat(digits.slice(i + 1).sort((a, b) => b - a)).join(''));

    return nextSmaller;
}
// Example usage
let number = 54321;
let nextSmaller = findNextSmallerInteger(number);
console.log(`The next smaller integer containing the same digits as ${number} is: ${nextSmaller}`);

В этой статье мы рассмотрели два метода поиска следующего меньшего по размеру положительного целого числа, содержащего те же цифры, что и заданное число. Подход грубой силы прост, но может быть неэффективен для больших чисел. С другой стороны, метод сортировки и замены предлагает более оптимизированное решение. Поняв эти методы, вы сможете эффективно решать подобные проблемы.