有序数组的平方
# 📃 题目描述
题目链接:977. 有序数组的平方 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给你一个按 非递减顺序 排序的整数数组 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]
# 🔔 解题思路
最简单的办法,遍历数组挨个平方后做排序,遍历的时间复杂度是 O(N),排序的时间复杂度就是 O(LogN) ,即这种暴力法的时间复杂度是 O(LogN),空间复杂度是 O(1)
还有一种时间复杂度 O(N) ,空间复杂度 O(N) 的方法:
由于数组中存在负数,负数平方之后可能比正数的平方要大。但是,数组的排序是有序的,也就是说,数组平方的最大值一定在数组的两端,不是最左边就是最右边,不可能是中间。
考虑用左右指针。左指针指向第一个元素,右指针指向最后一个元素。
这样,我们可以保证,随着左右指针的不断往中间靠拢,它们代表的平方数也越来越小。所以,我们只需要新建一个数组 res 用来存储最终的结果集,每次将左右指针比较出来的较大的结果从数组末端插入数组即可:
- 如果
nums[left]^2 > nums[right]^2
=> nums[left]l^2 加入 res 结果集,并 left ++; - 如果
nums[right]^2 >= nums[left]^2
=> nums[right]l^2 加入 res 结果集,并 right --;
class Solution {
public int[] sortedSquares(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int[] res = new int[nums.length];
// res 数组的下标
int index = nums.length - 1;
int left = 0;
int right = nums.length - 1;
// 注意这里是 left <= right, 因为最后要处理最后一个元素
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
res[index --] = nums[left] * nums[left];
left ++;
} else {
res[index --] = nums[right] * nums[right];
right --;
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10