题目来源
等 级 : 简 单
我 之 前 提 交 了 几 遍 结 果 答 案 错 误 , 吃 了 个 饭 回 来 一 看 就 出 来 了 说 明 什 么 ?
说 明 饿 了 就 要 去 干 饭 , 否 则 代 谢 跟 不 上
一、题目
给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题
二、代码及思路
思路:这里看到和前面我做的题是有共同点的,做的题都是数组的,前面我们讲过一个双指针法
,【leetcode】力扣 — 日积月累,每日一题——6 移除元素。仔细一看这里也可以用得到,那就来试试。
仔细阅读题:整个数组是从小到大有序排列的,在它的基础上进行平方。根据数学知识我们可以知道,
在x轴上趋向两端无穷大。那么平方之后,数组的最大值要么在最前面,要么在在后面。我们使用一个双
指针法,一个指向最前端,一个指向最后端,往中间走。注意left=right的时候是有意义的。
class Solution { public int[] sortedSquares(int[] nums) { int left = 0, right = nums.length - 1; int[] res = new int[nums.length]; int k = right; while(left <= right){ if(nums[left] * nums[left] > nums[right] * nums[right]){ res[k] = nums[left] * nums[left]; left++; k--; }else{ res[k--] = nums[right] * nums[right]; right--; } } return res; } }