ARTS 打卡第 3 周

2023-09-03
浙江
本文字数：908 字
阅读完需：约 3 分钟

题图摄于 2020 年 9 月 21 日广州大学城

1.Algorithm: 每周至少做一个 LeetCode 的算法题

题目：有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

'''示例'''输入：nums = [-4,-1,0,3,10]输出：[0,1,9,16,100]解释：平方后，数组变为 [16,1,0,9,100]排序后，数组变为 [0,1,9,16,100]
'''提示'''1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums 已按 非递减顺序 排序

复制代码

解法总结

核心就是前后双指针

    vector<int> sortedSquares(vector<int>& nums) {        int i = 0, j = nums.size() - 1;        vector<int> ans(nums.size(), 0);        for (int m = 0; m < nums.size(); i++) {            nums[m] = nums[m] * nums[m]; //先平方一遍        }        for (int n = nums.size() - 1; n >=0; n--) { //再前后数组元素比较            if (nums[i] < nums[j]) { //后面的大于前面的，那么这个ans末尾就放后面的，并且j--                ans[n] = nums[j];                j--;            }            else if (nums[i] >= nums[j]) {//前面的大于后面的，那么这个ans末尾就放前面的，并且i++                ans[n] = nums[i];                i++;            }        }        return ans;    }