977. 有序数组的平方#

题目描述#

题目链接: LeetCode 977

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

示例：

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

解题思路#

核心思想#

虽然原数组有序，但负数平方后会”翻转”大小：负数越靠左、平方越大，正数越靠右、平方越大。平方的最大值一定出在两端（最左或最右），因此用相向双指针，每次取出两端平方中较大者，从答案数组末尾向前填充，即可天然保证非递减。

算法步骤#

left = 0, right = n - 1, pos = n - 1
当 left <= right：
- 比较 nums[left]**2 与 nums[right]**2
- 把较大的填入 ans[pos]，并移动对应指针
- pos -= 1
返回 ans

逐步举例#

nums = [-4,-1,0,3,10]

left	right	平方比较	填入	pos
0	4	16 vs 100	100	4
0	3	16 vs 9	16	3
1	3	1 vs 9	9	2
1	2	1 vs 0	1	1
2	2	0 vs 0	0	0

结果为 [0,1,9,16,100]

复杂度分析#

时间复杂度：O(n)，一趟遍历
空间复杂度：O(1)，除答案数组外无额外空间

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def sortedSquares(self, nums: List[int]) -> List[int]:
6
        n = len(nums)
7
        ans = [0] * n
8
        left, right = 0, n - 1
9
        pos = n - 1
10
        while left <= right:
11
            l2 = nums[left] * nums[left]
12
            r2 = nums[right] * nums[right]
13
            if l2 > r2:
14
                ans[pos] = l2
15
                left += 1
16
            else:
17
                ans[pos] = r2
18
                right -= 1
19
            pos -= 1
20
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5

6
import unittest
7

8
from solution import Solution
9

10

11
class Test977(unittest.TestCase):
12
    def test_example1(self):
13
        self.assertEqual(
14
            Solution().sortedSquares([-4, -1, 0, 3, 10]),
15
            [0, 1, 9, 16, 100],
16
        )
17

18
    def test_example2(self):
19
        self.assertEqual(
20
            Solution().sortedSquares([-7, -3, 2, 3, 11]),
21
            [4, 9, 9, 49, 121],
22
        )
23

24
    def test_single(self):
25
        self.assertEqual(Solution().sortedSquares([-2]), [4])
26

27

28
if __name__ == '__main__':
29
    unittest.main()