文章目录
题目
标题和出处
标题：优美的排列 II
难度
7 级
题目描述
要求
给你两个整数 n \texttt{n} n 和 k \texttt{k} k，请你构造一个答案列表 answer \texttt{answer} answer，该列表应当包含从 1 \texttt{1} 1 到 n \texttt{n} n 的 n \texttt{n} n 个不同正整数，并同时满足下述条件：
- 假设该列表是 answer = [ a 1 , a 2 , a 3 , … , a n ] \texttt{answer} = [\texttt{a}_\texttt{1}, \texttt{a}_\texttt{2}, \texttt{a}_\texttt{3}, \ldots, \texttt{a}_\texttt{n}] answer=[a1,a2,a3,…,an]，那么列表 [ ∣ a 1 − a 2 ∣ , ∣ a 2 − a 3 ∣ , ∣ a 3 − a 4 ∣ , … , ∣ a n-1 − a n ∣ ] [|\texttt{a}_\texttt{1} - \texttt{a}_\texttt{2}|, |\texttt{a}_\texttt{2} - \texttt{a}_\texttt{3}|, |\texttt{a}_\texttt{3} - \texttt{a}_\texttt{4}|, \ldots, |\texttt{a}_\texttt{n-1} - \texttt{a}_\texttt{n}|] [∣a1−a2∣,∣a2−a3∣,∣a3−a4∣,…,∣an-1−an∣] 中应该有且仅有 k \texttt{k} k 个不同整数。
返回列表 answer \texttt{answer} answer。如果存在多种答案，只需返回其中任意一种。
示例
示例 1：
输入：
n
=
3,
k
=
1
\texttt{n = 3, k = 1}
n = 3, k = 1
输出：
[1,
2,
3]
\texttt{[1, 2, 3]}
[1, 2, 3]
解释：
[1,
2,
3]
\texttt{[1, 2, 3]}
[1, 2, 3] 包含
3
\texttt{3}
3 个范围在
1
\texttt{1}
1 到
3
\texttt{3}
3 的不同整数，并且
[1,
1]
\texttt{[1, 1]}
[1, 1] 中有且仅有
1
\texttt{1}
1 个不同整数：
1
\texttt{1}
1
示例 2：
输入：
n
=
3,
k
=
2
\texttt{n = 3, k = 2}
n = 3, k = 2
输出：
[1,
3,
2]
\texttt{[1, 3, 2]}
[1, 3, 2]
解释：
[1,
3,
2]
\texttt{[1, 3, 2]}
[1, 3, 2] 包含
3
\texttt{3}
3 个范围在
1
\texttt{1}
1 到
3
\texttt{3}
3 的不同整数，并且
[2,
1]
\texttt{[2, 1]}
[2, 1] 中有且仅有
2
\texttt{2}
2 个不同整数：
1
\texttt{1}
1 和
2
\texttt{2}
2
数据范围
- 1 ≤ k < n ≤ 10 4 \texttt{1} \le \texttt{k} < \texttt{n} \le \texttt{10}^\texttt{4} 1≤k<n≤104
解法
思路和算法
为了方便叙述，将列表 [ ∣ a 1 − a 2 ∣ , ∣ a 2 − a 3 ∣ , ∣ a 3 − a 4 ∣ , … , ∣ a n − 1 − a n ∣ ] [|a_1 - a_2|, |a_2 - a_3|, |a_3 - a_4|, \ldots, |a_{n-1} - a_n|] [∣a1−a2∣,∣a2−a3∣,∣a3−a4∣,…,∣an−1−an∣] 称为「相邻绝对差列表」。
对于从 1 1 1 到 n n n 的任意排列，对应的「相邻绝对差列表」中的不同整数最少为 1 1 1 个，即所有的相邻元素绝对差都相等，最多为 n − 1 n-1 n−1 个，即所有的相邻元素绝对差都不相等。
对于列表 [ 1 , 2 , 3 , … , n ] [1, 2, 3, \ldots, n] [1,2,3,…,n]，「相邻绝对差列表」中的元素都是 1 1 1，因此有 1 1 1 个不同整数。
对于列表 [ 1 , n , 2 , n − 1 , 3 , n − 2 , … ] [1, n, 2, n - 1, 3, n - 2, \ldots] [1,n,2,n−1,3,n−2,…]，「相邻绝对差列表」中的元素各不相同，分别为 n − 1 n-1 n−1 到 1 1 1，因此有 n − 1 n-1 n−1 个不同整数。
为了让「相邻绝对差列表」中的不同整数为 k k k 个，可以从整数 1 1 1 到 k + 1 k+1 k+1 构造出「相邻绝对差列表」中的元素各不相同的序列： [ 1 , k + 1 , 2 , k , 3 , k − 1 , … ] [1, k + 1, 2, k, 3, k - 1, \ldots] [1,k+1,2,k,3,k−1,…]，然后将从 k + 2 k+2 k+2 到 n n n 的整数依次添加到该序列的末尾。
按照上述方法构造出的序列，前 k + 1 k+1 k+1 个数的相邻元素绝对差各不相同，分别为 k k k 到 1 1 1，从 k + 2 k+2 k+2 到 n n n 的相邻元素绝对差都是 1 1 1， k + 2 k+2 k+2 前面的相邻元素一定大于 1 1 1，因此 k + 2 k+2 k+2 和前面的相邻元素的绝对差一定不超过 k k k。即整个序列的「相邻绝对差列表」包含从 1 1 1 到 k k k 的全部整数，且不包含大于 k k k 的整数，因此「相邻绝对差列表」中有且仅有 k k k 个不同整数。
证明
对于列表 [ 1 , n , 2 , n − 1 , 3 , n − 2 , … ] [1, n, 2, n - 1, 3, n - 2, \ldots] [1,n,2,n−1,3,n−2,…]，「相邻绝对差列表」中的元素各不相同，分别为 n − 1 n-1 n−1 到 1 1 1，有 n − 1 n-1 n−1 个不同整数。该结论证明如下。
用 arr \textit{arr} arr 表示列表 [ 1 , n , 2 , n − 1 , 3 , n − 2 , … ] [1, n, 2, n - 1, 3, n - 2, \ldots] [1,n,2,n−1,3,n−2,…]，则 arr \textit{arr} arr 中的每个下标对应的元素如下：
arr [ i ] = { i 2 + 1 , i 是 偶 数 n − i − 1 2 , i 是 奇 数 \textit{arr}[i]=\begin{cases} \dfrac{i}{2}+1, & i~是偶数 \\ n-\dfrac{i-1}{2}, & i~是奇数 \end{cases} arr[i]=⎩⎪⎨⎪⎧2i+1,n−2i−1,i 是偶数i 是奇数
当 1 ≤ i < n 1 \le i < n 1≤i<n 时， arr [ i ] − arr [ i − 1 ] \textit{arr}[i]-\textit{arr}[i-1] arr[i]−arr[i−1] 计算如下：
- 当 i i i 是奇数时：
arr [ i ] − arr [ i − 1 ] = ( n − i − 1 2 ) − ( i − 1 2 + 1 ) = n − ( i − 1 ) − 1 = n − i \begin{aligned} &\quad \ \textit{arr}[i]-\textit{arr}[i-1] \\ &= \Big(n-\dfrac{i-1}{2}\Big)-\Big(\dfrac{i-1}{2}+1\Big) \\ &= n-(i-1)-1 \\ &= n-i \end{aligned} arr[i]−arr[i−1]=(n−2i−1)−(2i−1+1)=n−(i−1)−1=n−i
- 当 i i i 是偶数时：
arr [ i − 1 ] − arr [ i ] = ( n − i − 2 2 ) − ( i 2 + 1 ) = n − ( i 2 − 1 ) − i 2 − 1 = n − i 2 + 1 − i 2 − 1 = n − i \begin{aligned} &\quad \ \textit{arr}[i-1]-\textit{arr}[i] \\ &= \Big(n-\dfrac{i-2}{2}\Big)-\Big(\dfrac{i}{2}+1\Big) \\ &= n-\Big(\dfrac{i}{2}-1\Big)-\dfrac{i}{2}-1 \\ &= n-\dfrac{i}{2}+1-\dfrac{i}{2}-1 \\ &= n-i \end{aligned} arr[i−1]−arr[i]=(n−2i−2)−(2i+1)=n−(2i−1)−2i−1=n−2i+1−2i−1=n−i
由于 1 ≤ i < n 1 \le i < n 1≤i<n，因此 1 ≤ n − i ≤ n − 1 1 \le n-i \le n-1 1≤n−i≤n−1， arr \textit{arr} arr 对应的「相邻绝对差列表」中的元素各不相同，分别为 n − 1 n-1 n−1 到 1 1 1。
代码
class Solution {
public int[] constructArray(int n, int k) {
int[] answer = new int[n];
int low = 1, high = k + 1;
for (int i = 0; i <= k; i++) {
if (i % 2 == 0) {
answer[i] = low++;
} else {
answer[i] = high--;
}
}
for (int i = k + 1; i < n; i++) {
answer[i] = i + 1;
}
return answer;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)。构造数组 answer \textit{answer} answer 的过程为遍历该数组一次，填入每个元素的时间为 O ( 1 ) O(1) O(1)，因此时间复杂度为 O ( n ) O(n) O(n)。
-
空间复杂度： O ( 1 ) O(1) O(1)。除了返回值以外，使用的空间复杂度是常数。