class Solution {
public:
vector<int> constructArray(int n, int k) {
}
};
667. 优美的排列 II
给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：
answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。
示例 1：
输入：n = 3, k = 1 输出：[1, 2, 3] 解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1
示例 2：
输入：n = 3, k = 2 输出：[1, 3, 2] 解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2
提示：
1 <= k < n <= 104
相似题目
原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 41.7 MB, 提交时间: 2022-11-29 12:16:00
class Solution {
public int[] constructArray(int n, int k) {
int[] answer = new int[n];
int idx = 0;
for (int i = 1; i < n - k; ++i) {
answer[idx] = i;
++idx;
}
for (int i = n - k, j = n; i <= j; ++i, --j) {
answer[idx] = i;
++idx;
if (i != j) {
answer[idx] = j;
++idx;
}
}
return answer;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.4 MB, 提交时间: 2022-11-29 12:15:44
func constructArray(n, k int) []int {
ans := make([]int, 0, n)
for i := 1; i < n-k; i++ {
ans = append(ans, i)
}
for i, j := n-k, n; i <= j; i++ {
ans = append(ans, i)
if i != j {
ans = append(ans, j)
}
j--
}
return ans
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 43.3 MB, 提交时间: 2022-11-29 12:15:26
/**
* @param {number} n
* @param {number} k
* @return {number[]}
*/
var constructArray = function(n, k) {
const answer = new Array(n).fill(0);
let idx = 0;
for (let i = 1; i < n - k; ++i) {
answer[idx] = i;
++idx;
}
for (let i = n - k, j = n; i <= j; ++i, --j) {
answer[idx] = i;
++idx;
if (i !== j) {
answer[idx] = j;
++idx;
}
}
return answer;
};
python3 解法, 执行用时: 48 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-29 12:15:12
class Solution:
def constructArray(self, n: int, k: int) -> List[int]:
answer = list(range(1, n - k))
i, j = n - k, n
while i <= j:
answer.append(i)
if i != j:
answer.append(j)
i, j = i + 1, j - 1
return answer