每日一题(2)

有序数组的平方

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> ans;for (int num: nums) {ans.push_back(num * num);}sort(ans.begin(), ans.end());return ans;}
};

这样写比较简单所以我抄的是官方的

这个方法就是把nums数组里面的元素拿出来然后给自身平方然后用sort进行快排后放回排序的数字

方法二用双指针的形式

是我自己的方法写的比较简略

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n=nums.size();vector<int>result=vector<int>(n,0);int left=0;int right=n-1;int k=n-1;while(left<=right){int x=nums[left];int y=nums[right];if(x*x>y*y){ result[k--]=x*x;left++;}else{result[k--]=y*y;right--;}}return result;}
};

这样的话时间复杂度都会低一点，开始先把nums里面的元素个数开辟一个新的vector用来存储排序后的元素，将left作为首下标的开始，将right作为尾下标的进行将x设为第首下标元素，y为尾下标的开始，开始进行比较大的放到新建result的最后面，小的不动直到left>right时将最后的元素放入result数组中

问题解惑：1.为什么left和right在数组的两边而不再中间或者是其他地方？

因为数组是排好序的可能从负数开始到正数结束这样的话最大的肯定在两边因为要进行平方这样的话比较起来方便

2.为什么left<=right而不是<,这个要看情况像这个例子假如数组中要全部填到数组中如果是1，2，3，4，5这样的话最后2，3，4，5填进去了此时left和right都指向了一的下标这样的话要将此时的1填进去就要保证left==right满足条件所以要包含

所以总的来说还是要注意细节谢谢观看