【数据结构与算法系列3】有序数组的平方 (C++ & Python)

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
3
4

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
1
2

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序
• 使用双指针算法

C++代码实现：

#include 
#include 

using namespace std;

vector sortedSquares(vector& nums) {
    int r_point = nums.size() - 1;
    vector result(nums.size(), 0);
    for (int slowpoint = 0, fasterpoint = nums.size() - 1; slowpoint <= fasterpoint;) {
        if (nums[slowpoint] * nums[slowpoint] > nums[fasterpoint] * nums[fasterpoint]) {
            result[r_point--] = nums[slowpoint] * nums[slowpoint];
            slowpoint++;
        }
        else
        {
            result[r_point--] = nums[fasterpoint] * nums[fasterpoint];
            fasterpoint--;
        }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

python实现：

from typing import List

def sortedSquares(nums: List):
    slowpoint = 0
    fasterpoint = len(nums) - 1
    r_point = len(nums) - 1
    results: List = [float('inf')] * len(nums) 

    while slowpoint <= fasterpoint:
        if nums[slowpoint] ** 2 > nums[fasterpoint] ** 2:
            results[r_point] = nums[slowpoint] ** 2
            r_point -= 1
            slowpoint += 1
        else:
            results[r_point] = nums[fasterpoint] ** 2
            r_point -= 1
            fasterpoint -= 1

    return results

if __name__ == "__main__":
    nums = [-23, -4, -3, 1, 2, 3, 4, 5, 9, 10, 12]
    print(sortedSquares(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23