Java&C++ 题解与拓展——leetcode667. 优美的排列 II【++ 在 java 和 C++ 中的差异】

2022 年 9 月 13 日
湖南
本文字数：1437 字
阅读完需：约 5 分钟

题目要求

思路：规律构造

本质上是数学推导，分别找到 k k 最小（ k=1 1 ）和最大（ k=n-1 ）的排列方式，然后分段构造即可。按升序（or 降序）排列，相邻项的差值均为 1 1 ，此时 k=1 1 ；按一大一小穿插排列，即奇数位升序偶数位降序（or 反过来）排列，如 [1,n,2,n-1,\dots] [ 1 , n , 2 , n − 1 , … ] ，此时 k=n-1 。
那么只要让序列一半升序一半穿插即可实现；先构造出所有差值，即 [1,k+1,2,k,\dots] [ 1 , k + 1 , 2 , k , … ] ；然后将剩余的数升序排列 [n-k,n-k+1,\dots,n] [ n − k , n − 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(1) O ( 1 ) ，忽略返回值

C++

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

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(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(1) O ( 1 ) ，忽略返回值

总结

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

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

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

欢迎指正与讨论！

发布于: 刚刚阅读数: 5

Java-fenn

关注

需要Java资料或者咨询可加我v ： Jimbye 2022.08.16 加入

还未添加个人简介

发布

暂无评论

创作场景

Java&C++ 题解与拓展——leetcode667. 优美的排列 II【++ 在 java 和 C++ 中的差异】

题目要求

思路：规律构造

Java

C++

Rust

总结

Java-fenn

评论