LeetCode刷题-有序数组的平方
2021-07-05 本文已影响0人
小鲨鱼FF
前言说明
算法学习,日常刷题记录。
题目连接
题目内容
给你一个按非递减顺序排序的整数数组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^4
nums 已按非递减顺序排序
进阶:
请你设计时间复杂度为O(n)的算法解决本问题
分析过程
利用双指针解决。
左指针从数组左侧开始,右指针从数组右侧开始,两个指针从数组两端往中间移动,直到两个指针相等,结束循环。
每次循环时,结果数组results只取较大的数,被取了数的一侧指针向中间移动一位,接着数组results再取较小的数,这侧的指针再向中间移动一位。
虽然是左右指针同时向中间移动,但是每次都会取两次的数,pos游标已经移动了两次,所以最后刚好构造出和数组nums的长度一致的结果数组results。
因为数组nums的绝对值两侧最大,往里越来越小,所以构造结果数组results时,从后往前构造,刚好就是非递减数组。
解答代码
class Solution {
public int[] sortedSquares(int[] nums) {
// 获取数组nums长度
int n = nums.length;
// 定义结果数组results
int[] results = new int[n];
// 用双指针遍历数组nums,从数组nums两边往里遍历,每次结果数组results只取大的数,结果数组results从后往前填满,直到两个指针游标相等
for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
// 若前指针i的位置的元素的平方大于后指针j的位置的元素的平方,那么前指针i移动
results[pos] = nums[i] * nums[i];
++i;
} else {
// 若前指针i的位置的元素的平方小于等于后指针j的位置的元素的平方,那么后指针j移动
results[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return results;
}
}
提交结果
执行用时1ms,时间击败100.00%的用户,内存消耗40.2MB,空间击败57.04%的用户。
运行结果原文链接
原文链接:有序数组的平方