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

本文主要是介绍每日一题 --- 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]

示例 2：

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

提示：

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

在这里插入图片描述

刚开始我的思路：

func sortedSquares(nums []int) []int {f, r := 0, len(nums)-1var 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
}

结果时间复杂度O(n²)，因为头插需要O(n)。
在这里插入图片描述

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

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

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

// 双指针
func sortedSquares(nums []int) []int {Len := len(nums)f, r := 0, Len-1arr := make([]int, Len)k := rfor k >= 0 {ones := nums[r] * nums[r]twos := nums[f] * nums[f]if ones >= twos {arr[k] = onesr--} else {arr[k] = twosf++}k--}return arr
}