『LeetCode』667 优美的排列 II

题目

667. 优美的排列 II

给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

假设该列表是 \(answer = [a_{1}, a_{2}, a_{3}, ... , a_{n}]\) ，那么列表 \([|a_{1} - a_{2}|, |a_{2} - a_{3}|, |a_{3} - a_{4}|, ... , |a_{n-1} - a_{n}|]\) 中应该有且仅有 \(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 <= 10^{4}\)

相似题目

优美的排列 (中等)

题解

【优美的排列 II】中等构造题

构造

既然题目要求结果中有且仅有 \(k\) 个整数，那么我们可以取 \(1, 2, ..., k\) 这 \(k\) 个数构造，将数组每 \(k + 1\) 个划分为一组，组内很容易构造出相邻数组差为 \(1, 2, ..., k\) 的整数如 \([i, i + k, i + 1, i + k - 1, ...]\), 而组间最大差值肯定不会超过 \(k\).

PS: 其实简单一点的话构造一组就够了，后面的递增排列即可

# Code language: Python
class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        # k 个不同的整数我们取 1, 2, ..., k
        ans = [0] * n
        p = 0
        for i in range(1, n + 1, k + 1):
            left, right = i, min(n, i + k)
            while left <= right:
                ans[p] = left
                left += 1
                p += 1
                if left > right: break
                ans[p] = right
                right -= 1
                p += 1
        # assert k == (s := len(Counter(abs(ans[i] - ans[i - 1]) for i in range(1, n)))), f"{k=}, {s=}" # 简单校验下结果正不正确
        return ans

// Code language: Java
class Solution {
    public int[] constructArray(int n, int k) {
        // k 个不同的整数我们取 1, 2, ..., k
        int[] ans = new int[n];
        for (int i = 1, p = 0; i <= n; i += k + 1) {
            for (int left = i, right = Math.min(n, i + k); left <= right; ) {
                ans[p++] = left;
                if (++left > right) break;
                ans[p++] = right--;
            }
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    vector<int> constructArray(int n, int k) {
        // k 个不同的整数我们取 1, 2, ..., k
        vector<int> ans(n);
        for (int i = 1, p = 0; i <= n; i += k + 1) {
            for (int left = i, right = min(n, i + k); left <= right; ) {
                ans[p++] = left;
                if (++left > right) break;
                ans[p++] = right--;
            }
        }
        return ans;
    }
};

/* Code language: JavaScript */
/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var constructArray = function(n, k) {
        // k 个不同的整数我们取 1, 2, ..., k
    const ans = new Array(n).fill(0);
    for (let i = 1, p = 0; i <= n; i += k + 1) {
        for (let left = i, right = Math.min(n, i + k); left <= right; ) {
            ans[p++] = left;
            if (++left > right) break;
            ans[p++] = right--;
        }
    }
    return ans;
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\), 忽略返回结果的空间开销 \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』667 优美的排列 II

题目

标签

相似题目

题解

构造