Сложность: medium
Супер некрасивое число — это положительное целое число, простые множители которого находятся в массиве primes.
Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число.
Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число.
Пример:
Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].
👨💻 Алгоритм:
1⃣Инициализация
Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes.
2⃣Генерация супер некрасивых чисел
Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly.
3⃣Возврат результата
Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом.
😎 Решение:
func nthSuperUglyNumber(n int, primes []int) int {
ugly_numbers := make([]int, n)
ugly_numbers[0] = 1
indices := make([]int, len(primes))
next_ugly := append([]int(nil), primes...)
for i := 1; i < n; i++ {
next_val := min(next_ugly)
ugly_numbers[i] = next_val
for j := 0; j < len(primes); j++ {
if next_val == next_ugly[j] {
indices[j]++
next_ugly[j] = ugly_numbers[indices[j]] * primes[j]
}
}
}
return ugly_numbers[n-1]
}
func min(arr []int) int {
minVal := arr[0]
for _, val := range arr {
if val < minVal {
minVal = val
}
}
return minVal
}Ставь 👍 и забирай 📚 Базу знаний