977. 有序数组的平方

题目:https://leetcode-cn.com/problems/squares-of-a-sorted-array/

代码:

class Solution {

    public int[] sortedSquares(int[] A) {
        int[] res = new int[A.length];
        int l=0;
        int r = A.length - 1;
        int i = res.length - 1;
        while (l <= r) {
            int nl = A[l] * A[l];
            int nr = A[r] * A[r];
            if (nl > nr) {
                res[i] = nl;
                l++;
            }else{
                res[i] = nr;
                r--;
            }
            i--;
        }

        return res;
    }

}

直接按照题目要求,先对A数组的每个值计算平方值,最后按照从小到大排序即可获得答案,但是这样效率太低,由于题目给定的数组A是有序的,我们可以好好利用这个条件进行优化。

1、因为数组A包含负数,且从小到大排序

2、平方值的大小跟绝对值有关

3、依照绝对值排序的话,A数组的特点是,两边大,中间小。根据这个特性我们可以对A数组进行排序

4、排序的时候可以顺便计算平方值,这样可以省去调用Math.pow()方法的时间消耗

最终得出上述代码,耗时1ms,击败100%的用户,666!

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏