LeetCode977-有序数组的平方

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/squares-of-a-sorted-array/

中文链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/

题目详述

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

示例 1：

1
2
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

1
2
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A 已按非递减顺序排序。

题目详解

数组已经有序，可以运用双指针。

  • 初始化两个指针分别指向数组的第一个和最后一个元素，在迭代的过程中指针往中间移动。
  • 另外还需要一个指向结果数组的指针，依次填入结果数组。
  • 比较两个指针所指元素的绝对值大小，填入结果数组，并移动指针。
  • 重复这个过程直至所有数据全部填入结果数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00977 {

    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int[] res = new int[n];
        int i = 0, j = n - 1, k = n - 1;
        while (i <= j) {
            if (Math.abs(A[i]) > Math.abs(A[j])) {
                res[k--] = A[i] * A[i];
                ++i;
            } else {
                res[k--] = A[j] * A[j];
                --j;
            }
        }
        return res;
    }
}