Given two integers n and k, construct a list answer that contains n
different positive integers ranging from 1 to n and obeys the following
requirement:
Suppose this list is answer = [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.
Return the listanswer. If there multiple valid answers, return any of
them.
Input: n =3, k =1Output: [1,2,3]Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer:1
Input: n =3, k =2Output: [1,3,2]Explanation: The [1,3,2] has three different positive integers ranging from 1 to 3, and the [2,1] has exactly 2 distinct integers:1 and 2.
The key idea is to create exactly k distinct absolute differences by alternating between the smallest and largest available numbers for the first k+1 positions, then filling the rest in order. This guarantees the required number of distinct differences.
classSolution {
public: vector<int> constructArray(int n, int k) {
vector<int> ans;
int l =1, r = n;
for (int i =0; i < k +1; ++i) {
if (i %2==0) ans.push_back(l++);
else ans.push_back(r--);
}
if ((k +1) %2==0) {
for (int i = r; i >= l; --i) ans.push_back(i);
} else {
for (int i = l; i <= r; ++i) ans.push_back(i);
}
return ans;
}
};
funcconstructArray(nint, kint) []int {
ans:= make([]int, 0, n)
l, r:=1, nfori:=0; i < k+1; i++ {
ifi%2==0 {
ans = append(ans, l)
l++ } else {
ans = append(ans, r)
r-- }
}
if (k+1)%2==0 {
fori:=r; i>=l; i-- {
ans = append(ans, i)
}
} else {
fori:=l; i<=r; i++ {
ans = append(ans, i)
}
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
publicint[]constructArray(int n, int k) {
int[] ans =newint[n];
int l = 1, r = n, idx = 0;
for (int i = 0; i < k + 1; i++) {
if (i % 2 == 0) ans[idx++]= l++;
else ans[idx++]= r--;
}
if ((k + 1) % 2 == 0) {
for (int i = r; i >= l; i--) ans[idx++]= i;
} else {
for (int i = l; i <= r; i++) ans[idx++]= i;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
funconstructArray(n: Int, k: Int): IntArray {
val ans = IntArray(n)
var l = 1var r = n
for (i in0..k) {
ans[i] = if (i % 2==0) l++else r-- }
if ((k + 1) % 2==0) {
for (i in r downTo l) ans[++k] = i
} else {
for (i in l..r) ans[++k] = i
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution:
defconstructArray(self, n: int, k: int) -> list[int]:
ans: list[int] = []
l, r =1, n
for i in range(k +1):
if i %2==0:
ans.append(l)
l +=1else:
ans.append(r)
r -=1if (k +1) %2==0:
ans.extend(range(r, l -1, -1))
else:
ans.extend(range(l, r +1))
return ans
impl Solution {
pubfnconstruct_array(n: i32, k: i32) -> Vec<i32> {
letmut ans = Vec::with_capacity(n asusize);
let (mut l, mut r) = (1, n);
for i in0..=k {
if i %2==0 {
ans.push(l);
l +=1;
} else {
ans.push(r);
r -=1;
}
}
if (k +1) %2==0 {
for i in (l..=r).rev() {
ans.push(i);
}
} else {
for i in l..=r {
ans.push(i);
}
}
ans
}
}