?667. 優(yōu)美的排列 II
難度：中等
給你兩個整數(shù) n 和 k ，請你構(gòu)造一個答案列表 answer ，該列表應(yīng)當(dāng)包含從 1 到 n 的 n 個不同正整數(shù)，并同時滿足下述條件：
假設(shè)該列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中應(yīng)該有且僅有 k 個不同整數(shù)。
返回列表 answer 。如果存在多種答案，只需返回其中 任意一種 。
示例 1：
輸入：n = 3, k = 1
輸出：[1, 2, 3]
解釋：[1, 2, 3] 包含 3 個范圍在 1-3 的不同整數(shù)，并且 [1, 1] 中有且僅有 1 個不同整數(shù)：1
示例 2：
輸入：n = 3, k = 2
輸出：[1, 3, 2]
解釋：[1, 3, 2] 包含 3 個范圍在 1-3 的不同整數(shù)，并且 [2, 1] 中有且僅有 2 個不同整數(shù)：1 和 2
提示：
- 1 < = k < n < = 1 0 4 1 <= k < n <= 10^4 1<=k<n<=104
??思路：
當(dāng) k=1 時，我們將 1～n 按照 [1,2,??,n]的順序進行排列，那么相鄰的差均為 1，滿足 k=1 的要求。
當(dāng) k=n?1 時，我們將 1～n 按照 [1, n, 2, n?1, 3, ??]的順序進行交叉排列，那么相鄰的差從 n?1 開始，依次遞減 1。這樣一來，所有從 1 到 n?1的差值均出現(xiàn)一次，滿足 k = n?1的要求。
所以對于其它的一般情況，我們可以將這兩種特殊情況進行合并，即列表的前半部分相鄰差均為 1，后半部分相鄰差從 k 開始逐漸遞減到 1，這樣從 1 到 k 的差值均出現(xiàn)一次，對應(yīng)的列表即為
[
1
,
2
,
?
,
n
?
k
,
n
,
n
?
k
+
1
,
n
?
1
,
n
?
k
+
2
,
?
]
[1,2,?,n?k,n,n?k+1,n?1,n?k+2,?]
[1,2,?,n?k,n,n?k+1,n?1,n?k+2,?]
??代碼：(Java、C++)
Java
class Solution {
public int[] constructArray(int n, int k) {
int[] ans = new int[n];
for(int i = 1; i <= n - k; i++){//前半部分相鄰差均為1
ans[i - 1] = i;
}
int low = n - k + 1;
int high = n;
int i = n - k;
while(low <= high){//后半部分交叉排序
ans[i++] = high--;
if(i >= n) break;
ans[i++] = low++;
}
return ans;
}
}
C++
class Solution {
public:
vector<int> constructArray(int n, int k) {
vector<int> ans(n);
for(int i = 1; i <= n - k; i++){//前半部分相鄰差均為1
ans[i - 1] = i;
}
int low = n - k + 1;
int high = n;
int i = n - k;
while(low <= high){//后半部分交叉排序
ans[i++] = high--;
if(i >= n) break;
ans[i++] = low++;
}
return ans;
}
};
?? 運行結(jié)果：
?? 復(fù)雜度分析：
- 時間復(fù)雜度： O ( n ) O(n) O(n)。
- 空間復(fù)雜度： O ( 1 ) O(1) O(1)，這里不計入返回值需要的空間，只需常數(shù)級空間。
題目來源：力扣。文章來源：http://www.zghlxwxcb.cn/news/detail-455460.html
放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我 leetCode專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-455460.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于( 數(shù)組和矩陣) 667. 優(yōu)美的排列 II ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
