0667-优美的排列 II

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你两个整数 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

方法一：从特殊情况到一般情况

思路与算法

当 k=1 时，我们将 1 \sim n 按照 [1, 2, \cdots, n] 的顺序进行排列，那么相邻的差均为 1，满足 k=1 的要求。

当 k=n-1 时，我们将 1 \sim n 按照 [1, n, 2, n-1, 3, \cdots] 的顺序进行排列，那么相邻的差从 n-1 开始，依次递减 1。这样一来，所有从 1 到 n-1 的差值均出现一次，满足 k=n-1 的要求。

对于其它的一般情况，我们可以将这两种特殊情况进行合并，即列表的前半部分相邻差均为 1，后半部分相邻差从 k 开始逐渐递减到 1，这样从 1 到 k 的差值均出现一次，对应的列表即为：

[1, 2, \cdots, n-k, n, n-k+1, n-1, n-k+2, \cdots]

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> answer;
        for (int i = 1; i < n - k; ++i) {
            answer.push_back(i);
        }
        for (int i = n - k, j = n; i <= j; ++i, --j) {
            answer.push_back(i);
            if (i != j) {
                answer.push_back(j);
            }
        }
        return answer;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public 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;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
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
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int* constructArray(int n, int k, int* returnSize){
    int *answer = (int *)malloc(sizeof(int) * n);
    int pos = 0;
    for (int i = 1; i < n - k; ++i) {
        answer[pos++] = i;
    }
    for (int i = n - k, j = n; i <= j; ++i, --j) {
        answer[pos++] = i;
        if (i != j) {
            answer[pos++] = j;
        }
    }
    *returnSize = n;
    return answer;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)，这里不计入返回值需要的空间。

 Comments
On this page
0667-优美的排列 II