有序数组的平方


题目

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

示例 1:

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

分析

同样,我们很容易想到: 先给这个数组来个平方放入新的数组, 然后对新的数组做排序就好了。因为要用到排序,所以时间复杂度不可能为 O(n) 。

但题目给定数组为 非递减 数组,即一个有序数组。

也就是说,当我们给每个数平方时(如果该数组含有负数) , 则最大值必然在最左或者最右,然后向中间递减。

按照这个特性,我们可以考虑通过 双指针 来做这件事情。

左指针 left 从最左往最右走, 右指针 right 从最右往最左走。每次比较最指针的平方值 leftSquare 和 右指针的平方值 rightSquare ,将最大的值放到新数组的最右边,然后将相应的指针移动一步,直到左指针 left 大于右指针 right

代码

 private static int[] sortedSquares(int[] ary) {
        // 双指针, 是一种很有用的方法
        // 从左右两边分别往中间移动
        int left = 0;
        int right = ary.length - 1;

        // 用于标记下一个元素需要插入的位置
        int idx = right;
        int[] result = new int[ary.length];

        while (left <= right) {
            int leftSquare = ary[left] * ary[left];
            int rightSquare = ary[right] * ary[right];
            if (leftSquare >= rightSquare) {
                left++;
                result[idx--] = leftSquare;
            } else {
                right--;
                result[idx--] = rightSquare;
            }
        }
        return result;
    }

文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
合并两个有序数组 合并两个有序数组
题目 给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。 要求时间复杂度为 O(n) 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n
2020-10-18
下一篇 
每日事毕 每日事毕
每日事毕前几日, 与老友前往宝石山爬山。约在了早上九点。 已然约摸 30 岁的年纪,但仍旧孑然一身,有时不免有些惭愧,但不在此时。 大概七点多,我起来洗漱完,就开始导航如何到达目的地。首选必然是地铁,只是看到地铁需要约 90 分钟,当时不知
2020-10-16
  目录