两端收缩遍历，双指针构造列表，求解《667. 优美的排列 II》
例题
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
答案
双指针 · 两端收缩遍历
var constructArray = function(n, k) {
const ans = new Array(n)
let pos = 0, l = 1, r = k + 1
while (l < r) {
ans[pos++] = l++
ans[pos++] = r--
}
if (l === r) ans[pos++] = l
while (pos < n) ans[pos++] = ++k + 1
return ans
};function constructArray(n: number, k: number): number[] {
const ans = new Array(n)
let pos = 0, l = 1, r = k + 1
while (l < r) {
ans[pos++] = l++
ans[pos++] = r--
}
if (l === r) ans[pos++] = l
while (pos < n) ans[pos++] = ++k + 1
return ans
};class Solution {
function constructArray($n, $k) {
$ans = array_fill(0, $n, 0);
$l = 1;
$r = $k + 1;
$pos = 0;
while ($l < $r) {
$ans[$pos++] = $l++;
$ans[$pos++] = $r--;
}
if ($l === $r) $ans[$pos++] = $l;
while ($pos < $n) $ans[$pos++] = ++$k + 1;
return $ans;
}
}func constructArray(n int, k int) []int {
ans, l, r, pos := make([]int, n), 1, k + 1, 0
for l < r {
ans[pos], pos, l = l, pos + 1, l + 1
ans[pos], pos, r = r, pos + 1, r - 1
}
if l == r {
ans[pos], pos = l, pos + 1
}
for pos < n {
ans[pos], pos, k = k + 2, pos + 1, k + 1
}
return ans
}class Solution {
public int[] constructArray(int n, int k) {
int[] ans = new int[n];
int l = 1, r = k + 1, pos = 0;
while (l < r) {
ans[pos++] = l++;
ans[pos++] = r--;
}
if (l == r) ans[pos++] = l;
while (pos < n) ans[pos++] = ++k + 1;
return ans;
}
}public class Solution {
public int[] ConstructArray(int n, int k) {
int[] ans = new int[n];
int l = 1, r = k + 1, pos = 0;
while (l < r) {
ans[pos++] = l++;
ans[pos++] = r--;
}
if (l == r) ans[pos++] = l;
while (pos < n) ans[pos++] = ++k + 1;
return ans;
}
}int* constructArray(int n, int k, int* returnSize){
int* ans = malloc(sizeof(int) * n);
int l = 1, r = k + 1, pos = 0;
while (l < r) {
ans[pos++] = l++;
ans[pos++] = r--;
}
if (l == r) ans[pos++] = l;
while (pos < n) ans[pos++] = ++k + 1;
*returnSize = pos;
return ans;
}class Solution {
public:
vector<int> constructArray(int n, int k) {
vector<int> ans(n);
int l = 1, r = k + 1, pos = 0;
while (l < r) {
ans[pos++] = l++;
ans[pos++] = r--;
}
if (l == r) ans[pos++] = l;
while (pos < n) ans[pos++] = ++k + 1;
return ans;
}
};class Solution:
def constructArray(self, n: int, k: int) -> List[int]:
ans, l, r, pos = [0] * n, 1, k + 1, 0
while l < r:
ans[pos], pos, l = l, pos + 1, l + 1
ans[pos], pos, r = r ,pos + 1, r - 1
if l == r: ans[pos], pos = l, pos + 1
while pos < n: ans[pos], pos, k = k + 2, pos + 1, k + 1
return ans迭代 · 交换变量
var constructArray = function(n, k) {
const ans = Array.from({length: n}, (_, i) => i + 1)
for (l = 1; l < k; l += 2) {
for (let r = k; r > l; r--) {
swap(ans, r - 1, r)
}
}
return ans
};
const swap = (nums, a, b) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}