Сложность: 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.
😎 Решение:
func constructArray(_ n: Int, _ k: Int) -> [Int] {
var answer = [Int]()
var left = 1, right = n
for i in 0...k {
if i % 2 == 0 {
answer.append(left)
left += 1
} else {
answer.append(right)
right -= 1
}
}
if k % 2 == 0 {
answer += left...right
} else {
answer += (left...right).reversed()
}
return answer
}Ставь 👍 и забирай 📚 Базу знаний