leetcode【977-有序数组的平方】思考、优化、改进

ゝ一纸荒年。 2023-01-04 14:49 89阅读 0赞

leetcode【977-有序数组的平方】思考、优化、改进  
 声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！  
  又是一道很简单的题目，应该第一时间都会使用如下方法，遍历平方加上STL的sort函数。这种方法没啥思考，三行直接解决。

vector<int> sortedSquares(vector<int>& nums) { 
            for(int i=0;i<nums.size();i++)
                nums[i]=nums[i]*nums[i];
            sort(nums.begin(), nums.end());
            return nums;
        }
    执行用时：156 ms, 在所有 C++ 提交中击败了9.76%的用户
    内存消耗：25.9 MB, 在所有 C++ 提交中击败了8.35%的用户

结局也是不出所料。。这种方法太垃圾了。  
开始想了很久并没有发现特别好的方法，直到看了看官方的题解：  
**题目中说数组说该数组已然是升序排列！所以我们可以有以下思路：**  
 1. 找 到 原 始 数 组 中 正 负 元 素 的 分 界 点 \\color\{\#FF0000\}\{1.找到原始数组中正负元素的分界点\} 1.找到原始数组中正负元素的分界点  
 2. 可 以 直 到 ， 这 两 个 数 组 各 自 已 经 是 升 序 排 列 ， 我 们 只 需 要 将 他 们 组 合 成 一 个 程 序 的 数 组 即 可 \\color\{\#FF0000\}\{2.可以直到，这两个数组各自已经是升序排列，我们只需要将他们组合成一个程序的数组即可\} 2.可以直到，这两个数组各自已经是升序排列，我们只需要将他们组合成一个程序的数组即可  
 Q ： 想 到 了 什 么 ？ ？ 这 是 不 是 一 次 归 并 排 序 啊 ？ 我 们 不 需 要 用 s o r t 函 数 了 ， 我 们 用 双 指 针 搞 个 一 次 的 归 并 排 序 是 不 是 就 可 以 了 ？ 不 再 赘 述 ， 上 代 码 \\color\{\#FF0000\}\{Q：想到了什么？？这是不是一次归并排序啊？我们不需要用sort函数了，我们用双指针搞个一次的归并排序是不是就可以了？不再赘述，上代码\} Q：想到了什么？？这是不是一次归并排序啊？我们不需要用sort函数了，我们用双指针搞个一次的归并排序是不是就可以了？不再赘述，上代码  
 3. 是 不 是 一 个 双 指 针 问 题 ？ 并 且 v e c 首 是 第 一 个 序 列 的 最 大 值 ， v e c 尾 是 第 二 个 序 列 的 最 大 值 ？ \\color\{\#FF0000\}\{3.是不是一个双指针问题？并且vec首是第一个序列的最大值，vec尾是第二个序列的最大值？\} 3.是不是一个双指针问题？并且vec首是第一个序列的最大值，vec尾是第二个序列的最大值？  
好了直接上一下官方解题，这个还是写的很简洁漂亮的，值得学习。

vector<int> sortedSquares(vector<int>& A) { 
            int n = A.size();
            vector<int> ans(n);
            for (int i = 0, j = n - 1, pos = n - 1; i <= j;) { 
                if (A[i] * A[i] > A[j] * A[j]) { 
                    ans[pos] = A[i] * A[i];
                    ++i;
                }
                else { 
                    ans[pos] = A[j] * A[j];
                    --j;
                }
                --pos;
            }
            return ans;
        }