0667. Beautiful Arrangement II

题目信息

题号:

0667

难度:

Medium

主题:

排列、相邻绝对差、不同差值数量、构造任意答案

原题:

LeetCode 0667

重点:

数组必须恰好是 1 到 n 的排列、统计相邻绝对差的不同数值、需要恰好得到 k 种差值、可返回任意合法排列

题目重述

给定整数 n 和 k,构造长度为 n 的数组 answer。数组必须包含整数 1 到 n 各一次;对每个相邻位置计算 |answer[i] - answer[i+1]|,这些差值中必须恰好出现 k 个不同数值。

返回任意一个满足条件的排列。n 位于 [2, 10^4],k 位于 [1, n-1],题目保证答案存在。

自建示例

产生三种不同相邻差:

输入:n = 5,k = 3
输出:[1,4,2,3,5]
解释:相邻绝对差依次为 3、2、1、2,不同差值集合正好是 {1,2,3};其他合法排列也可以返回。

只需要一种差值:

输入:n = 4,k = 1
输出:[1,2,3,4]
解释:所有相邻绝对差都是 1,因此恰好只有一种不同差值。