每日一题做题记录，参考官方和三叶的题解

题目要求

思路：规律构造

• 本质上是数学推导，分别找到kkk最小（k=1k=1k=1）和最大（k=n−1k=n-1k=n−1）的排列方式，然后分段构造即可。
  • 按升序（or降序）排列，相邻项的差值均为111，此时k=1k=1k=1；
  • 按一大一小穿插排列，即奇数位升序偶数位降序（or反过来）排列，如[1,n,2,n−1,… ][1,n,2,n-1,\dots][1,n,2,n−1,…]，此时k=n−1k=n-1k=n−1。
• 那么只要让序列一半升序一半穿插即可实现；
  • 先构造出所有差值，即[1,k+1,2,k,… ][1,k+1,2,k,\dots][1,k+1,2,k,…]；
  • 然后将剩余的数升序排列[n−k,n−k+1,…,n][n-k,n-k+1,\dots,n][n−k,n−k+1,…,n]；
  • 二者直接拼合即可，交界处的差值必定在前半段出现过，所以对答案没有影响。

Java

【是谁忘了判断越界错了半天，首先排除我自己】

class Solution {
    public int[] constructArray(int n, int k) {
        int[] res = new int[n];
        // 前半段
        for (int i = 0, l = 1, r = k + 1; i < k + 1; ) {
            res[i++] = l++; // 一小
            if (i < k + 1) // 避免越界
                res[i++] = r--; // 一大
        }
        //后半段
        for (int i = k + 1; i < n; )
            res[i] = ++i;
        return res;
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)，忽略返回值

C++

• 发现了有趣的事，++i在java和C++中的运行顺序是不同的，
  • java中是先固定了等式前半段再去++然后赋值给之前定好的位置；
  • C++是先++然后赋值给新的位置。
• 去查了一下发现其实i++也会有同样的问题，参考链接：
  • C++在运行时，变量和值都在内存中一起存取计算，所以“一荣俱荣”；
  • java运行时存在堆栈，等式前半段（赋值目标中的iii）会先压入堆栈，然后进行计算再赋值。

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> res(n);
        // 前半段
        for (int i = 0, l = 1, r = k + 1; i < k + 1; ) {
            res[i++] = l++; // 一小
            if (i < k + 1) // 避免越界
                res[i++] = r--; // 一大
        }
        //后半段
        for (int i = k + 1; i < n; i++)
            res[i] = i + 1;
        return res;
    }
};

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)，忽略返回值

Rust

impl Solution {
    pub fn construct_array(n: i32, k: i32) -> Vec<i32> {
        let mut res = vec![0; n as usize];
        let (mut i, mut l, mut r) = (0, 1, k + 1);
        // 前半段
        while i < k + 1 {
            res[i as usize] = l; // 一小
            i += 1;
            l += 1;
            if i < k + 1 { // 避免越界
                res[i as usize] = r; // 一大
                i += 1;
                r -= 1;
            }
        }
        // 后半段
        for j in k + 1..n {
            res[j as usize] = j + 1;
        }
        res
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)，忽略返回值

总结

刚开始没仔细看题，以为是随机给nnn个数构造，头都大了两圈，看到示例还想这咋净举这么简单的例子，脑子里走马灯了半天发现原来今儿👀没上班。

这个构造思路属于是猛然一下迸发灵感，然后发现和题解一样，贼快乐~

还发现了没好好学语言运行原理而搞出来的溢出小问题，进而学习了自增在不同语言中的运行原理。

欢迎指正与讨论！