【双指针-简单】977. 有序数组的平方

【题目】
提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
1
2
3

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题
1

【代码】

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        right,left=len(nums),0
        for idx,item in enumerate(nums):
            if item>=0:                
                right=idx
                break
        rr=right
        left=right-1
        ans=[]
        while rr<len(nums) and left>=0:
            if nums[rr]<=abs(nums[left]):                
                ans.append(nums[rr]**2)
                rr+=1
            else:
                ans.append(nums[left]**2)
                left-=1
        while rr<len(nums):
            ans.append(nums[rr]**2)
            rr+=1
        while left>=0:
            ans.append(nums[left]**2)
            left-=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【方法2】

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left,right=0,len(nums)-1
        ans=[]
        while left<=right:
            l=nums[left]**2
            r=nums[right]**2
            if l>=r:
                ans.insert(0,l)
                left+=1
            else:
                ans.insert(0,r)
                right-=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left,right=0,len(nums)-1
        ans=[0 for i in range(len(nums))]
        pos=len(nums)-1
        while left<=right:
            l=nums[left]**2
            r=nums[right]**2
            if l>=r:
                ans[pos]=l
                left+=1
            else:
                ans[pos]=r
                right-=1
            pos-=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16