算法题/双指针：对排序后的数组进行平方

题目

给定一个已排序的数组，创建一个新数组，其中包含输入数组中所有按排序顺序排列的数字的平方。

示例1：

输入：[-2, -1, 0, 2, 3]
输出：[0, 1, 4, 4, 9]
解释：元素平方后依然有序

示例2：

输入：[-3, -1, 0, 1, 2]
输出：[0, 1, 1, 4, 9]
解释：元素平方后依然有序

解答1：

Java

class SortedArraySquares {

  public static int[] makeSquares(int[] arr) {
    int n = arr.length;
    int[] squares = new int[n];
    int highestSquareIdx = n - 1;
    int left = 0, right = arr.length - 1;
    while (left <= right) {
      int leftSquare = arr[left] * arr[left];
      int rightSquare = arr[right] * arr[right];
      if (leftSquare > rightSquare) {
        squares[highestSquareIdx--] = leftSquare;
        left++;
      } else {
        squares[highestSquareIdx--] = rightSquare;
        right--;
      }
    }
    return squares;
  }

  public static void main(String[] args) {

    int[] result = SortedArraySquares.makeSquares(new int[] { -2, -1, 0, 2, 3 });
    for (int num : result)
      System.out.print(num + " ");
    System.out.println();

    result = SortedArraySquares.makeSquares(new int[] { -3, -1, 0, 1, 2 });
    for (int num : result)
      System.out.print(num + " ");
    System.out.println();
  }
}

JavaScript

class SortedArraySquares {
    static makeSquares(arr) {
        const n = arr.length;
        const squares = new Array(n);
        let highestSquareIdx = n - 1;
        let left = 0, right = arr.length - 1;
        while (left <= right) {
            const leftSquare = arr[left] * arr[left];
            const rightSquare = arr[right] * arr[right];
            if (leftSquare > rightSquare) {
                squares[highestSquareIdx--] = leftSquare;
                left++;
            } else {
                squares[highestSquareIdx--] = rightSquare;
                right--;
            }
        }
        return squares;
    }
}

const result1 = SortedArraySquares.makeSquares([-2, -1, 0, 2, 3]);
for (const num of result1) {
    console.log(num);
}

const result2 = SortedArraySquares.makeSquares([-3, -1, 0, 1, 2]);
for (const num of result2) {
    console.log(num);
}

Python

class SortedArraySquares:
    def makeSquares(arr):
        n = len(arr)
        squares = [0] * n
        highestSquareIdx = n - 1
        left, right = 0, n - 1
        while left <= right:
            leftSquare = arr[left] * arr[left]
            rightSquare = arr[right] * arr[right]
            if leftSquare > rightSquare:
                squares[highestSquareIdx] = leftSquare
                highestSquareIdx -= 1
                left += 1
            else:
                squares[highestSquareIdx] = rightSquare
                highestSquareIdx -= 1
                right -= 1
        return squares


result1 = SortedArraySquares.makeSquares([-2, -1, 0, 2, 3])
for num in result1:
    print(num, end=" ")

print()

result2 = SortedArraySquares.makeSquares([-3, -1, 0, 1, 2])
for num in result2:
    print(num, end=" ")

print()

Go

package main

import "fmt"

type SortedArraySquares struct{}

func (s *SortedArraySquares) makeSquares(arr []int) []int {
	n := len(arr)
	squares := make([]int, n)
	highestSquareIdx := n - 1
	left, right := 0, n-1
	for left <= right {
		leftSquare := arr[left] * arr[left]
		rightSquare := arr[right] * arr[right]
		if leftSquare > rightSquare {
			squares[highestSquareIdx] = leftSquare
			highestSquareIdx--
			left++
		} else {
			squares[highestSquareIdx] = rightSquare
			highestSquareIdx--
			right--
		}
	}
	return squares
}

func main() {
	s := SortedArraySquares{}

	result1 := s.makeSquares([]int{-2, -1, 0, 2, 3})
	for _, num := range result1 {
		fmt.Printf("%d ", num)
	}
	fmt.Println()

	result2 := s.makeSquares([]int{-3, -1, 0, 1, 2})
	for _, num := range result2 {
		fmt.Printf("%d ", num)
	}
	fmt.Println()
}