977. 有序数组的平方

🟢   🔖  数组 双指针 排序  🔗 力扣 LeetCode

题目

Given an integer array nums sorted in non-decreasing order, return an array ofthe squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]

Output: [0,1,9,16,100]

Explanation: After squaring, the array becomes [16,1,0,9,100].

After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

题目大意

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题。

解题思路

1. 平方和排序:

   • 负数的平方会变成正数，所以需要将负数和正数的平方进行比较。
   • 对于一个已经排好序的数组，负数的平方值在数组前部（较小的绝对值），正数的平方值在数组后部（较大的绝对值）。因此可以利用双指针的方式从两端开始，比较左右两侧的平方值并按升序放入结果数组。

2. 初始化:

   • 初始化一个和输入数组同样长度的结果数组 res。
   • 使用两个指针 left 和 right，分别指向数组的两端。
   • 变量 i 用于指示当前填充位置，由于结果数组需要按升序排列，所以从数组的末尾（最大位置）开始填充。

3. 填充结果数组:

   • 每次比较 nums[left] 和 nums[right] 的绝对值大小，较大的平方值填入结果数组的末尾，并更新对应的指针（left 或 right）。
   • 当左右指针交错时，循环结束，最终得到的数组就是按升序排列的平方数组。

复杂度分析

• 时间复杂度: O(n)，双指针法遍历整个数组，每个元素都只访问一次。
• 空间复杂度: O(n)，构造了一个大小为 n 的结果数组 res。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
	const n = nums.length;
	let res = new Array(n);
	let left = 0,
		right = n - 1;
	let i = n - 1;
	while (left <= right) {
		if (Math.abs(nums[left]) > Math.abs(nums[right])) {
			res[i--] = nums[left] ** 2;
			left++;
		} else {
			res[i--] = nums[right] ** 2;
			right--;
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
88	合并两个有序数组	[✓]	数组 双指针 排序	🟢	🀄️ 🔗
360	有序转化数组 🔒		数组 数学 双指针 1+	🟠	🀄️ 🔗