Сложность: medium
Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:
Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.
Пример:
Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1
👨💻 Алгоритм:
1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].
2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.
3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.
😎 Решение:
fun constructArray(n: Int, k: Int): IntArray {
val answer = mutableListOf<Int>()
var left = 1
var right = n
for (i in 0..k) {
if (i % 2 == 0) {
answer.add(left)
left++
} else {
answer.add(right)
right--
}
}
if (k % 2 == 0) {
for (i in left..right) answer.add(i)
} else {
for (i in right downTo left) answer.add(i)
}
return answer.toIntArray()
}Ставь 👍 и забирай 📚 Базу знаний