LeetCode 0977. 有序数组的平方
原创LeetCode 0977. 有序数组的平方
原创
Yano_nankai
修改于 2021-02-20 18:03:41
修改于 2021-02-20 18:03:41
题目描述
给你一个按 非递减顺序 排序的整数数组 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 <= 10^4-10^4 <= nums[i] <= 10^4nums 已按 非递减顺序 排序进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题解题思路
可以使用暴力求解，即最后需要对平方后的数组 res 进行排序，时间复杂度为 O(nlogn)。
题目的进阶要求是时间复杂度为 O(n)，其实也比较简单，先遍历出数组绝对值最小的，依次向两边遍历即可（题目已经说明输入的数组是非递减顺序的）。
代码
public int[] sortedSquares(int[] A) {
int[] res = new int[A.length];
for (int i = 0; i < A.length; i++) {
res[i] = A[i] * A[i];
}
Arrays.sort(res);
return res;
}复杂度分析
时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
