题目

给你一个按 非递减顺序 排序的整数数组 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 已按 非递减顺序 排序

题解

第一反应是排序，但这时间复杂度肯定压不住了。然后考虑到由于数组本身是有序的，所以尝试用双指针的方法来解决这个问题。

首先用一个循环找到第一个大于等于 0 的元素的下标，然后用两个指针分别指向这个元素和它前面的元素。然后比较这两个元素的平方，较小的那个结果 append 到结果数组。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func sortedSquares(nums []int) []int {
	ptrA := len(nums)
	for i, num := range nums {
		if num >= 0 {
			ptrA = i
			break
		}
		nums[i] = -nums[i]
	}

	res := make([]int, 0, len(nums))
	for ptrB := ptrA - 1; ptrB > -1 || ptrA < len(nums); {
		if ptrA == len(nums) {
			res = append(res, nums[ptrB]*nums[ptrB])
			ptrB--
		} else if ptrB == -1 {
			res = append(res, nums[ptrA]*nums[ptrA])
			ptrA++
		} else if nums[ptrA] < nums[ptrB] {
			res = append(res, nums[ptrA]*nums[ptrA])
			ptrA++
		} else {
			res = append(res, nums[ptrB]*nums[ptrB])
			ptrB--
		}
	}

	return res
}

时间复杂度是 O(n)，空间复杂度是 O(n)。

这里一开始在第二个循环的退出条件上写错了，应该是 ptrB > -1 || ptrA < len(nums)，而不是 ptrB > -1 && ptrA < len(nums)。因为如果 ptrB 和 ptrA 都到达了数组的边界，循环就会退出，而我们需要在这两者中至少有一个还在数组的范围内。这里卡了一段时间，最后也是通过打印的方式才反应过来的。应该说是一个很低级的错误，并且编写的时候想到了这个问题，但写代码的时候还是出现了错误。

基于上面的思路，可以继续思考。上面之所以需要先进行一个循环来找到第一个大于等于 0 的元素，是因为我们需要知道这个元素的下标，然后从小到大放置平方后的元素。而实际上可以转换视角，考虑从大到小放置平方后的元素。这样就不需要先进行一个循环来找到第一个大于等于 0 的元素了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func sortedSquares(nums []int) []int {
	res := make([]int, len(nums))
	for i, ptrA, ptrB := len(nums)-1, 0, len(nums)-1; i > -1; i-- {
		if ptrA == len(nums) {
			res[i] = nums[ptrB] * nums[ptrB]
			ptrB--
		} else if ptrB == -1 {
			res[i] = nums[ptrA] * nums[ptrA]
			ptrA++
		} else if powA, powB := nums[ptrA]*nums[ptrA], nums[ptrB]*nums[ptrB]; powA > powB {
			res[i] = powA
			ptrA++
		} else {
			res[i] = powB
			ptrB--
		}
	}

	return res
}