Leetcode 977. Squares of a Sorted Array
题目解法1：two pass with two pointer解法2：improved two pass with two pointers解法3：one pass with two pointers
题目
解法1：two pass with two pointer
class Solution:
def sortedSquares(self
, A
: List
[int]) -> List
[int]:
for i
in range(len(A
)):
if A
[i
]>=0:
divide_pos
= i
break
array1
= A
[:i
][::-1]
array2
= A
[i
:]
p1
= p2
= 0
ans
= []
while p1
<len(array1
) and p2
<len(array2
):
if array1
[p1
]**2 < array2
[p2
]**2:
ans
.append
(array1
[p1
]**2)
p1
+= 1
else:
ans
.append
(array2
[p2
]**2)
p2
+=1
while p1
<len(array1
):
ans
.append
(array1
[p1
]**2)
p1
+= 1
while p2
<len(array2
):
ans
.append
(array2
[p2
]**2)
p2
+= 1
return ans
解法2：improved two pass with two pointers
改进了空间复杂度 直接比较绝对值节省时间
class Solution:
def sortedSquares(self
, A
: List
[int]) -> List
[int]:
for i
in range(len(A
)):
if A
[i
]>=0:
divide_pos
= i
break
p2
= i
p1
= i
-1
ans
= []
while p1
>=0 and p2
<len(A
):
if abs(A
[p1
]) < abs(A
[p2
]):
ans
.append
(A
[p1
]**2)
p1
-= 1
else:
ans
.append
(A
[p2
]**2)
p2
+=1
while p1
>=0:
ans
.append
(A
[p1
]**2)
p1
-= 1
while p2
<len(A
):
ans
.append
(A
[p2
]**2)
p2
+= 1
return ans
解法3：one pass with two pointers
class Solution:
def sortedSquares(self
, A
: List
[int]) -> List
[int]:
ans
= [0]*len(A
)
l
= 0
r
= len(A
)-1
p
= len(A
)-1
while l
<=r
:
if abs(A
[l
])<abs(A
[r
]):
ans
[p
] = A
[r
]**2
p
-= 1
r
-= 1
else:
ans
[p
] = A
[l
]**2
p
-= 1
l
+= 1
return ans
C++版本
class Solution {
public:
vector
<int> sortedSquares(vector
<int>& A
) {
int n
= A
.size();
vector
<int> ans(n
,0);
int l
= 0, r
= n
- 1, p
= n
- 1;
while(l
<=r
){
if(abs(A
[l
]) < abs(A
[r
])){
ans
[p
] = A
[r
]*A
[r
];
r
--;
}else{
ans
[p
] = A
[l
]*A
[l
];
l
++;
}
p
--;
}
return ans
;
}
};
