leetcode 977 有序数组的平方

￡神魔★判官ぃ 2022-09-07 06:14 161阅读 0赞

## 前言 ##

题目：[977. 有序数组的平方][977.]

参考答案：[有序数组的平方-力扣官方题解][-]、[有序数组的平方-代码随想录][- 1]

--------------------

## 提交代码 ##

### 暴力解 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    class Solution {
    public:
        vector<int> sortedSquares(vector<int>& nums) {
            // 暴力解，先平方，后排序；时间复杂度O(nlogn)
            for(auto &num : nums) 
                num*=num;
            sort(nums.begin(),nums.end());
            return nums;
        }
    };
    
    int main(void){
        vector<int> nums = {-7,-3,2,3,11};
        Solution s;
        s.sortedSquares(nums);
        for(auto tmp:nums)
            cout<<tmp<<" ";
    }

### 双指针 ###

平方的最大值，来自头的平方或尾的平方。

下面第一个代码是我最开始版本的进阶代码，但是它的逻辑存在问题。问题的根源在于，没有使用附加空间，在原始空间上交换，存在逻辑错误。第二个代码使用附加空间，则顺利解决问题。

class Solution {
        // 错误实现，反例：[-5,-3,-2,-1]
    public:
        // vector<int> sortedSquares(vector<int>& nums) {
        //     //for_each(nums.begin(),nums.end(),abs); //这样写会报错，因为没有指定abs函数使用何种类型的重载
        //     // 折腾半天，也没搞定，你可以参考下面两个链接试试
        //     // https://stackoverflow.com/questions/12638166/g-compiler-error-couldnt-deduce-template-parameter-funct
        //     // https://stackoverflow.com/questions/14270475/for-each-and-transform
        //     for_each(nums.begin(),nums.end(),[](int& a) {a= a<0 ? -a:a;}); // 预处理数据，对每个元素取绝对值
            
        //     int left=0,right=nums.size()-1;
        //     while(left <= right){
        //         if(nums[left] <= nums[right]){
        //             nums[right]*=nums[right];
        //             right--;
        //         }else{
        //             swap(nums[left],nums[right]);
        //             nums[right]*=nums[right];
        //             right--;
        //         }
        //     }
        //     return nums;
        // }
    
        // 上面代码结构优化下
        vector<int> sortedSquares(vector<int>& nums) {
            for_each(nums.begin(),nums.end(),[](int& a) {a= a<0 ? -a:a;}); // 预处理数据，对每个元素取绝对值
            
            int left=0,right=nums.size()-1;
            while(left <= right){
                if(nums[left] > nums[right])
                    swap(nums[left],nums[right]); // 这里错了
                nums[right]*=nums[right];
                right--;
            }
            return nums;
        }
    };

下面是正确的代码思路。

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

### 合并两个有序表 ###

在负数与非负数的分界线两侧，分别平方之后，仍然满足单增/单减。剩下的事情便是合并两个有序表。

class Solution {
    public:
        vector<int> sortedSquares(vector<int>& nums) {
            // 查询第一个大于等于0的位置
            vector<int>::iterator it = lower_bound(nums.begin(),nums.end(),0);
            int negative = distance(nums.begin(),it);
            
            // 合并两个有序表
            int len = nums.size();
            int i=negative-1,j=negative;
            vector<int> ans;
            while(i>=0 || j<len){
                if(i<0){
                    ans.push_back(nums[j]*nums[j]);
                    j++;
                }else if(j>=len){
                    ans.push_back(nums[i]*nums[i]);
                    i--;
                }else if(nums[i]*nums[i] < nums[j]*nums[j]){
                    ans.push_back(nums[i]*nums[i]);
                    i--;
                }else{
                    ans.push_back(nums[j]*nums[j]);
                    j++;
                }
            }
            
            return ans;
        }
    };

[977.]: https://leetcode-cn.com/problems/squares-of-a-sorted-array/
[-]: https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
[- 1]: https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/dai-ma-sui-xiang-lu-shu-zu-ti-mu-zong-ji-1rtz/