每日一题 --- 977. 有序数组的平方[力扣][Go]

今天这一题和昨天的知识点是一样的，就是双指针法。
题目：

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
3
4

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
1
2

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

刚开始我的思路：

func sortedSquares(nums []int) []int {
	f, r := 0, len(nums)-1
	var arr = []int{}
	for f <= r {
		ones := nums[r] * nums[r]
		twos := nums[f] * nums[f]
		if ones <= twos {
			arr = insertHead(arr, twos)
			f++
		} else {
			arr = insertHead(arr, ones)
			r--
		}
	}
	return arr
}

func insertHead(arr []int, n int) []int {
	arr = append([]int{n}, arr...)
	return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

结果时间复杂度O(n²)，因为头插需要O(n)。

代码随想录中有O(log(n))的解法，有兴趣的可以去看看。

链接放这里了：代码随想录 (programmercarl.com)

不过咱们还是直接看O(n)的算法实现吧。

// 双指针
func sortedSquares(nums []int) []int {
   Len := len(nums)
   f, r := 0, Len-1
   arr := make([]int, Len)
   k := r
   for k >= 0 {
      ones := nums[r] * nums[r]
      twos := nums[f] * nums[f]
      if ones >= twos {
         arr[k] = ones
         r--
      } else {
         arr[k] = twos
         f++
      }
      k--
   }
   return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

从两头开始标记，指针平方大的先复制再往里走，直到所有值赋完。