Leetcode 977. Squares of a Sorted Array (python+cpp)

题目

解法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 = ibreakarray1 = A[:i][::-1]array2 = A[i:]p1 = p2 = 0ans = []while p1<len(array1) and p2<len(array2):if array1[p1]**2 < array2[p2]**2:ans.append(array1[p1]**2)p1 += 1else:ans.append(array2[p2]**2)p2 +=1while p1<len(array1):ans.append(array1[p1]**2)p1 += 1while p2<len(array2):ans.append(array2[p2]**2)p2 += 1return 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 = ibreakp2 = ip1 = i-1ans = []while p1>=0 and p2<len(A):if abs(A[p1]) < abs(A[p2]):ans.append(A[p1]**2)p1 -= 1else:ans.append(A[p2]**2)p2 +=1while p1>=0:ans.append(A[p1]**2)p1 -= 1while p2<len(A):ans.append(A[p2]**2)p2 += 1return ans

解法3：one pass with two pointers

class Solution:def sortedSquares(self, A: List[int]) -> List[int]:ans = [0]*len(A)l = 0r = len(A)-1p = len(A)-1while l<=r:if abs(A[l])<abs(A[r]):ans[p] = A[r]**2p -= 1r -= 1else:ans[p] = A[l]**2p -= 1l += 1return 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;}
};