Leetcode-977-有序数组的平方

Leecode-977. 有序数组的平方https://leetcode-cn.com/problems/rotting-oranges/)

思路：双指针

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

思路： 双指针

class Solution {
    public int[] sortedSquares(int[] A) {
        int length;
        if(A == null || (length = A.length) == 0){
            return new int[]{0};
        }

        // 双指针
        int i = 0;
        int j = length - 1;
        int k = length - 1;

        // 结果集
        int[] result = new int[length];

        // 遍历 一遍数组
        while(i <= j){
            int temp;

            if(A[i] * A[i] > A[j] * A[j]){
                temp = A[i] * A[i];
                i++;
            }else{
                temp = A[j] * A[j];
                j--;
            }

            result[k--] = temp;
        }
        return result;
    }
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

打赏