算法刷题笔记【数组】977.有序数组的平方

算法刷题笔记【数组】977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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.暴力解法

思路：先求平方，再调用排序函数，复杂度为快排的量级

// 1.暴力解法

// c++
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
            nums[i] *= nums[i];
        }

        sort(nums.begin(), nums.end());
        return nums;
    }
};


//---------------------------------------

// C
int cmp(const void* e1, const void* e2) {
    return *(int*)e1 - *(int*)e2;
}

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* ans = (int *)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; ++i) {
        ans[i] = nums[i] * nums[i];
    }
    qsort(ans, numsSize, sizeof(int), cmp);
    return ans;
}

2.从中间分界点往两边找

思路：先找到负数和非负数的分界点，使用两个指针从中间往两边找，小的先加入数组

注意：

​ 1.运算符的优先级，(*returnSize)++ 和 *returnSize++ 的区别

​ 2.原数组 完全逆序 和 完全升序 的处理

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        int n = nums.size();
        int idx = -1;
        // 找到最小值下标
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                idx = i;
            } else {
                break;
            }
        }
        vector<int> ans;
        int i = idx, j = idx + 1;
        while (i >= 0 || j < n) {
            if (i < 0) { // 等价于 j == 0
                // 说明原数组只有非零正数，求平方之后也是非递减数组
                ans.push_back(nums[j] * nums[j]);
                ++j;
            } else if (j == n) { // 等价于 i == n - 1
                // 说明原数组都是负数，求平方之后是递减数组
                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;
    }
};

// C

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    // 1. 找到负数与非负数分界点
    int flag = -1;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] < 0) {
            flag = i;
        } else {
            break;
        }
    }
    // 2. 创建新数组
    int* ans = (int *)malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    // 3. 双指针循环边对比边往两边找
    int l = flag, r = flag + 1;
    while (l >= 0 || r < numsSize) {   //左闭右开
        if (l < 0) {
            ans[(*returnSize)++] = nums[r] * nums[r];
            ++r;
        } else if (r == numsSize) {
            ans[(*returnSize)++] = nums[l] * nums[l];
            --l;
        } else if (nums[l] * nums[l] < nums[r] * nums[r]) {
            ans[(*returnSize)++] = nums[l] * nums[l];
            --l;
        } else {
            ans[(*returnSize)++] = nums[r] * nums[r];
            ++r;
        }
    }

    // 4. 处理返回值
    return ans;
}

3.双指针相向而行

思路：从两边往中间找，大的优先放在后边

注意：

​ 1.数组（容器）要进行初始化长度

​ 2.查找下标为闭区间，条件用小于等于

/************************************************************************
> File Name:        0923 sortedSquares.cpp
> Author:           leon-ais
> Mail:             leon_ais@qq.com
> Created Time:     Fri 23 Sep 2022 05:43:48 PM CST
> Description:      
************************************************************************/
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        // 1.创建新数组
        int n = nums.size();
        vector<int> ans(n);

        // 2.计算平方
        for (int i = 0; i < n; ++i) {
            nums[i] *= nums[i];
        }

        // 3.双指针相向而行
        int i = 0, j = n - 1, idx = n-1;
        while (i <= j) {
            if (nums[i] > nums[j]) {
                ans[idx--] = nums[i++];
            } else {
                ans[idx--] = nums[j--];
            }
        }

        return ans;
    }
};


/************************************************************************
> File Name:        0923 sortedSquares.cpp
> Author:           leon-ais
> Mail:             leon_ais@qq.com
> Created Time:     Fri 23 Sep 2022 05:43:48 PM CST
> Description:      
************************************************************************/
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        // 1.创建新数组
        int n = nums.size();
        vector<int> ans(n);

        int i = 0, j = n - 1, idx = n - 1;
        while (i <= j) {
            if (-nums[i] > nums[j]) {
                ans[idx--] = nums[i] * nums[i];
                ++i;
            } else {
                ans[idx--] = nums[j] * nums[j];
                --j;
            }
        }

        return ans;
    }
};

// C

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    // 1. 创建新数组
    int* ans = (int *)malloc(sizeof(int) * numsSize);
    *returnSize = numsSize;
    // 2. 计算平方值
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = nums[i] * nums[i];
    }
    // 3. 双指针循环从两边往中间找
    int l = 0, r = numsSize - 1, i = *returnSize - 1;
    while (l <= r) {   //左闭右开
        if (nums[l] < nums[r]) {
            ans[i--] = nums[r--];
        } else {
            ans[i--] = nums[l++];
        }
    }

    // 4. 处理返回值
    return ans;

小结

最直观的想法，莫过于：每个数平方之后，排个序，美滋滋

这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度，但为了和下面双指针法算法时间复杂度有鲜明对比，我记为 O(n + nlog n)。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j];

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i];

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。