每日一题 --- 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
}

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

这篇关于每日一题 --- 977. 有序数组的平方[力扣][Go]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---