В этой статье блога мы углубимся в увлекательную задачу поиска следующего меньшего положительного целого числа, содержащего те же цифры, что и заданное число. Мы рассмотрим различные методы и предоставим примеры кода для демонстрации каждого подхода. Итак, берите свой любимый напиток и начнем!
Метод 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}`);
В этой статье мы рассмотрели два метода поиска следующего меньшего по размеру положительного целого числа, содержащего те же цифры, что и заданное число. Подход грубой силы прост, но может быть неэффективен для больших чисел. С другой стороны, метод сортировки и замены предлагает более оптимизированное решение. Поняв эти методы, вы сможете эффективно решать подобные проблемы.