算法刷題筆記【數(shù)組】977.有序數(shù)組的平方

給你一個按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。

示例 1： 輸入：nums = [-4,-1,0,3,10] 輸出：[0,1,9,16,100] 解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]，排序后，數(shù)組變?yōu)?[0,1,9,16,100]

示例 2： 輸入：nums = [-7,-3,2,3,11] 輸出：[4,9,9,49,121]

1.暴力解法

思路：先求平方，再調(diào)用排序函數(shù)，復(fù)雜度為快排的量級

// 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.從中間分界點往兩邊找

思路：先找到負(fù)數(shù)和非負(fù)數(shù)的分界點，使用兩個指針從中間往兩邊找，小的先加入數(shù)組

注意：

1.運算符的優(yōu)先級，(*returnSize)++ 和 *returnSize++ 的區(qū)別

2.原數(shù)組 完全逆序 和 完全升序 的處理

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

        int n = nums.size();
        int idx = -1;
        // 找到最小值下標(biāo)
        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
                // 說明原數(shù)組只有非零正數(shù)，求平方之后也是非遞減數(shù)組
                ans.push_back(nums[j] * nums[j]);
                ++j;
            } else if (j == n) { // 等價于 i == n - 1
                // 說明原數(shù)組都是負(fù)數(shù)，求平方之后是遞減數(shù)組
                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. 找到負(fù)數(shù)與非負(fù)數(shù)分界點
    int flag = -1;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] < 0) {
            flag = i;
        } else {
            break;
        }
    }
    // 2. 創(chuàng)建新數(shù)組
    int* ans = (int *)malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    // 3. 雙指針循環(huán)邊對比邊往兩邊找
    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.雙指針相向而行

思路：從兩邊往中間找，大的優(yōu)先放在后邊

注意：

1.數(shù)組（容器）要進行初始化長度

2.查找下標(biāo)為閉區(qū)間，條件用小于等于

/************************************************************************
> 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.創(chuàng)建新數(shù)組
        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.創(chuàng)建新數(shù)組
        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. 創(chuàng)建新數(shù)組
    int* ans = (int *)malloc(sizeof(int) * numsSize);
    *returnSize = numsSize;
    // 2. 計算平方值
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = nums[i] * nums[i];
    }
    // 3. 雙指針循環(huán)從兩邊往中間找
    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;

小結(jié)

最直觀的想法，莫過于：每個數(shù)平方之后，排個序，美滋滋

這個時間復(fù)雜度是 O(n + nlogn)， 可以說是O(nlogn)的時間復(fù)雜度，但為了和下面雙指針法算法時間復(fù)雜度有鮮明對比，我記為 O(n + nlog n)。

數(shù)組其實是有序的， 只不過負(fù)數(shù)平方之后可能成為最大數(shù)了。

那么數(shù)組平方的最大值就在數(shù)組的兩端，不是最左邊就是最右邊，不可能是中間。

此時可以考慮雙指針法了，i指向起始位置，j指向終止位置。

定義一個新數(shù)組result，和A數(shù)組一樣的大小，讓k指向result數(shù)組終止位置。

如果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];

此時的時間復(fù)雜度為O(n)，相對于暴力排序的解法O(n + nlog n)還是提升不少的。