Сложность: medium
Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:
Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.
Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.
Пример:
Input: n = 12
Output: 21
👨💻 Алгоритм:
1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.
2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.
3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.
😎 Решение:
class Solution {
private func swap(_ s: String, _ i0: Int, _ i1: Int) -> String {
if i0 == i1 {
return s
}
var chars = Array(s)
chars.swapAt(i0, i1)
return String(chars)
}
private var list = [String]()
private func permute(_ a: String, _ l: Int, _ r: Int) {
if l == r {
list.append(a)
} else {
var a = a
for i in l...r {
a = swap(a, l, i)
permute(a, l + 1, r)
a = swap(a, l, i)
}
}
}
func nextGreaterElement(_ n: Int) -> Int {
let s = String(n)
permute(s, 0, s.count - 1)
list.sort()
if let index = list.firstIndex(of: s), index < list.count - 1 {
if let result = Int(list[index + 1]), result <= Int32.max {
return result
}
}
return -1
}
}Ставь 👍 и забирай 📚 Базу знаний