• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Leetcode—977. 有序数组的平方

开发技术 开发技术 4小时前 3次浏览

简单

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

示例 1:

输入:nums = [-4,-1,0,3,10]

输出:[0,1,9,16,100]

解释:平方后,数组变为 [16,1,0,9,100]

排序后,数组变为 [0,1,9,16,100]
示例 2:

输入:nums = [-7,-3,2,3,11]

输出:[4,9,9,49,121]
 

提示:

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序
 

进阶:

请你设计时间复杂度为 O(n) 的算法解决本问题

思路:

使用双指针的方式,从两头往中间走,比对比的结果放到另一个结果表里。

 static int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int k = right;
        while (left <= right) {//left大于right,两个指标已经相遇过了
            int lsum = nums[left] * nums[left];
            lsum = lsum < 0 ? -lsum : lsum;
            int rsum = nums[right] * nums[right];
            rsum = rsum < 0 ? -rsum : rsum;
            if (rsum > lsum) {
                result[k--] = rsum;
                right--;
            } else {
                result[k--] = lsum;
                left++;
            }
        }

        return result;
    }

程序员灯塔
转载请注明原文链接:Leetcode—977. 有序数组的平方
喜欢 (0)