Medium

题目描述

给定两个整数 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 <= 10^4

解题思路

这道题的关键在于理解如何构造出恰好有 k 个不同差值的数组。

核心观察：

  1. 如果数组是连续递增的（如[1,2,3,4,5]），那么所有相邻差值都是1，只有1个不同差值
  2. 如果数组在最大值和最小值之间交替（如[1,5,2,4,3]），可以产生多种不同的差值

解法思路： 采用"交替构造"的策略：

  1. 先放置前 k+1 个数字，通过在最小值和最大值之间交替来产生 k 个不同的差值
  2. 剩余的数字按顺序排列，确保它们的差值都是1（已经包含在前面的差值中）

具体步骤：

  • 使用 low = 1, high = k+1 进行交替放置
  • 第一次放 low，第二次放 high，第三次放 low+1，第四次放 high-1…
  • 这样可以产生差值：k, k-1, k-2, …, 1
  • 最后将剩余数字 [k+2, k+3, …, n] 按顺序添加

这种方法保证了恰好有 k 个不同的差值，且构造过程简单高效。

代码实现

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> result;
        int low = 1, high = k + 1;
        
        // 交替放置前k+1个数字，产生k个不同差值
        for (int i = 0; i < k + 1; i++) {
            if (i % 2 == 0) {
                result.push_back(low++);
            } else {
                result.push_back(high--);
            }
        }
        
        // 按顺序添加剩余数字
        for (int i = k + 2; i <= n; i++) {
            result.push_back(i);
        }
        
        return result;
    }
};

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        result = []
        low, high = 1, k + 1
        
        # 交替放置前k+1个数字，产生k个不同差值
        for i in range(k + 1):
            if i % 2 == 0:
                result.append(low)
                low += 1
            else:
                result.append(high)
                high -= 1
        
        # 按顺序添加剩余数字
        for i in range(k + 2, n + 1):
            result.append(i)
        
        return result

public class Solution {
    public int[] ConstructArray(int n, int k) {
        int[] result = new int[n];
        int low = 1, high = k + 1;
        int index = 0;
        
        // 交替放置前k+1个数字，产生k个不同差值
        for (int i = 0; i < k + 1; i++) {
            if (i % 2 == 0) {
                result[index++] = low++;
            } else {
                result[index++] = high--;
            }
        }
        
        // 按顺序添加剩余数字
        for (int i = k + 2; i <= n; i++) {
            result[index++] = i;
        }
        
        return result;
    }
}

var constructArray = function(n, k) {
    const result = [];
    let low = 1, high = k + 1;
    
    for (let i = 0; i <= k; i++) {
        if (i % 2 === 0) {
            result.push(low++);
        } else {
            result.push(high--);
        }
    }
    
    for (let i = k + 2; i <= n; i++) {
        result.push(i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历构造n个数字
空间复杂度O(1)除了返回数组外，只使用常数额外空间

相关题目