Leetcode977:有序数组的平方——双指针

题目

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

题解

先平方再排序

class Solution {
public:
    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;

    }
};

没啥好说的，打败40%的用户😂

双指针

不难发现，一个一般的nums数组前面是负数后面是正数，nums数组平方后的最大值一是第一个元素或最后一个元素。所以在第一位和最后一位分别放两个指针i和j。

判断if nums[i]*nums[i] > nums[j]*nums[j]，则把nums[i]*nums[i]放到res数组最后一位，否则把nums[j]*nums[j]放到最后一位。然后往前移动i，或者往后移动j。

这里有个动画：977.有序数组的平方.gif

代码：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = 0;
        int j = nums.size()-1;
        int k = j;
        vector<int> res(nums.size());
        while(i<=j){
            if(nums[i]*nums[i] <= nums[j]*nums[j]){
                res[k--] = nums[j]*nums[j];
                j--;
            }else{
                res[k--] = nums[i]*nums[i];
                i++;
            }
        }
    return res;
    }
};

细节：

• 因为可能i和j所指的元素相等，所以判断里要加个等于
• while循环停止的条件，可以是i<=j，或许也可以是k>=0 ?