建设淘宝网站,学校门户网站建设需要多少费用,网页界面设计的原则有哪些,卖产品的网站怎么做每日一题(LeetCode)----数组–有序数组的平方
1.题目#xff08;[977. 有序数组的平方](https://leetcode.cn/problems/sqrtx/)#xff09;
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。…每日一题(LeetCode)----数组–有序数组的平方
1.题目[977. 有序数组的平方](https://leetcode.cn/problems/sqrtx/)
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10]
输出[0,1,9,16,100]
解释平方后数组变为 [16,1,0,9,100]
排序后数组变为 [0,1,9,16,100]示例 2
输入nums [-7,-3,2,3,11]
输出[4,9,9,49,121]提示
1 nums.length 104-104 nums[i] 104nums 已按 非递减顺序 排序
进阶
请你设计时间复杂度为 O(n) 的算法解决本问题
2.解题思路
思路一 双指针法
通过观察发现正数包括零平方后从左向右递增负数平方后从右向左递增所以我们先找到第一个不是负数的位置然后找到最后一个负数的位置将这组数进行平方操作,并放到一个新创建的vector中最后从第一个不是负数的位置向左遍历最后一个负数的位置向右遍历将这两个指针遍历到的数进行比较然后依次往原有vector中放入排序好的元素注意如果某一指针移至边界了那么就将另一指针还未遍历到的数依次放入到原有vector中排好序的元素的后面。
思路二 双指针法
我们可以使用两个指针分别指向位置 0 和 n−1每次比较两个指针对应的数选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况读者可以仔细思考其精髓所在。
原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/
3.写出代码
思路一的代码
class Solution {
public:vectorint sortedSquares(vectorint nums) {int length nums.size();int poIndex -1;//找到第一个不是负数的下标for (int i 0; i length; i) {if (nums[i] 0) {poIndex i;break;}}//找到最后一个负数的下标int neIndex;if (poIndex -1) {neIndex nums.size()-1;}else {neIndex poIndex - 1;}//将这组数进行平方操作,并放到一个新创建的vector中vectorint Temp;for (int i 0; i length; i) {Temp.push_back(nums[i] * nums[i]);}//从中间往两边进行比较然后依次往原有vector中放入排序好的元素int i 0;while ((poIndex ( nums.size() - 1)) neIndex0) {if (Temp[poIndex] Temp[neIndex]) {nums[i] Temp[neIndex--];}else {nums[i] Temp[poIndex];}}while (poIndex nums.size() - 1) {nums[i] Temp[poIndex];}while (neIndex 0) {nums[i] Temp[neIndex--];}return nums;}
};思路二的代码
class Solution {
public:vectorint sortedSquares(vectorint nums) {int n nums.size();vectorint ans(n);for (int i 0, j n - 1, pos n - 1; i j;) {if (nums[i] * nums[i] nums[j] * nums[j]) {ans[pos] nums[i] * nums[i];i;}else {ans[pos] nums[j] * nums[j];--j;}--pos;}return ans;}
};作者力扣官方题解
链接https://leetcode.cn/problems/squares-of-a-sorted-array/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/
