LC-977
2024-09-08 13:35:35
给你一个按 非递减顺序 排序的整数数组 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)
的算法解决本问题
Related Topics
- 数组
- 双指针
- 排序
官方的解法是先找到正负分界下标,双指针是从分界往两边,小的值放入结果数组头部。
也可以, 双指针从两边往中间,大的值放入结果数组尾部, 不用事先遍历数组求正负分界下标,不过在俩个指针相遇前都需要对两个指针位置的数组值做平方运行,而官方的解法只要有一端走到头部或者尾部,就不用做平方和比较了,把没走完的一端的值依次放进数组就好,或者直接做数组拷贝,在一些原数组正负值数量差距较大的效率可能会有差异。
public int[] sortedSquares(int[] nums) {
// 左指针,指向原数组最左边
int left = 0;
// 有指针,指向原数组最右边
int right = nums.length - 1;
// 创建一个新数组,存储平方值
int[] result = new int[nums.length];
// 得到元素值平方值,从新数组最后位置开始写
int write = nums.length - 1;
// 左右指针相遇(逐渐靠拢的过程)之后不再循环
while (left <= right){
// 如果原数组的左指针对应的平方值大于右指针,那么往新数组最后位置写入左指针对应的平方值
if (nums[left] * nums[left] > nums[right] * nums[right]){
result[write] = nums[left] * nums[left];
// 左指针右移
left ++;
// 移动新数组待写入的位置
write --;
}
else {
result[write] = nums[right] * nums[right];
right --;
write --;
}
}
return result;
}
最新文章
- yii2权限控制rbac之rule详细讲解
- 高介分类:核方法与支持向量机(SVM)
- ASP.NET MVC WEB API字段出现k__BackingField
- 【python】用setup安装自定义模块和包
- Redis内存使用优化与存储
- [No000005]C#注册表操作,创建,删除,修改,判断节点是否存在
- jquery的扩展之extend函数
- 关于ul和dl的区别
- TensorFlow框架之Computational Graph详解
- IDL 数组运算
- Java-ServletResponse-ServletResponseWrapper
- arr.sort()
- redis make编译失败的原因
- MetaMask/metamask-extension/mascara 的运行实现
- jdk1.8 HashMap红黑树操作详解-putTreeVal()
- 解决 ionic 中的 CORS(跨域)
- python中的*arg和**kwargs
- 通过Referer设置来防盗链
- grep 详解
- jquery的常用操作(操作html页面的Dom对象的元素)